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

 

Apartments

There are n$n$ applicants and m$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$n$, m$m$, and k$k$: the number of applicants, the number of apartments, and the maximum allowed difference.

The next line contains n$n$ integers a1,a2,…,an$a_1,a_2,\dots ,a_n$: the desired apartment size of each applicant. If the desired size of an applicant is x$x$, he or she will accept any apartment whose size is between x−k$x-k$ and x+k$x+k$.

The last line contains m$m$ integers b1,b2,…,bm$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≤n,m≤2⋅105$1\le n,m\le 2\cdot {10}^5$
  
• 0≤k≤109$0\le k\le {10}^9$
  
• 1≤ai,bi≤109$1\le a_i,b_i\le {10}^9$
  

Example

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

Output:
2