CSES Apartments Solution C++ with Explanation | CSES Problem Set

 

Apartments

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 nm, and k: the number of applicants, the number of apartments, and the maximum allowed difference.

The next line contains n integers a1,a2,,an: 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 xk and x+k.

The last line contains m integers b1,b2,,bm: the size of each apartment.

Output

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

Constraints
  • 1n,m2105
  • 0k109
  • 1ai,bi109
Example

Input:
4 3 5
60 45 80 60
30 60 75


Output:
2

Post a Comment

0 Comments