CSES - Apartments | Căn hộ

View as PDF



Authors:
Problem types
Points: 1200 (p) Time limit: 1.0s Memory limit: 512M Input: stdin Output: stdout

There are \(n\) applicants and \(m\) free apartments. Your task is to distribute the apartments so that as many applicants as possible will get an apartment.

Each applicant has a desired apartment size, and they will accept any apartment whose size is close enough to the desired size.

Input

  • The first input line has three integers \(n\), \(m\) and \(k\): the number of applicants, the number of apartments, and the maximum allowed difference.
  • The next line contains \(n\) integers \(a_1,a_2,\dots, a_n\): the desired apartment size of each applicant. If the desired size of an applicant is \(x\), he or she will accept any apartment whose size is between \(x−k\) and \(x+k\).
  • The last line contains \(m\) integers \(b_1,b_2,\dots,b_m\): the size of each apartment.

Output

  • Print one integer: the number of applicants who will get an apartment.

Constraints

  • \(1 \leq n, m \leq 2 \cdot 10^5\)
  • \(0 \leq k \leq 10^9\)
  • \(1 \leq a_i, b_i \leq 10^9\)

Example

Sample input

4 3 5
60 45 80 60
30 60 75

Sample output
2


Comments (4)

Most recent
Loading comments...