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

The next line contains nnn integers a1,a2,…,ana_1, a_2, \ldots, a_na1,a2,…,an: the desired apartment size of each applicant. If the desired size of an applicant is xxx, he or she will accept any apartment whose size is between x−kx-kx−k and x+kx+kx+k.

The last line contains mmm integers b1,b2,…,bmb_1, b_2, \ldots, b_mb1,b2,…,bm: the size of each apartment.

# Output

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

# Constraints

1≤n,m≤2⋅1051 \le n, m \le 2 \cdot 10^51≤n,m≤2⋅105

0≤k≤1090 \le k \le 10^90≤k≤109

1≤ai,bi≤1091 \le a_i, b_i \le 10^91≤ai,bi≤109

# Example

Input:

```
4 3 5
60 45 80 60
30 60 75
```

Output:

```
2
```

# Solution:

In this problem, we have **n** applicants and **m** free appartments, the task is to distribute the apratments so that as many applicants as gets an apartment.

We can see from above that the number of applicants who will get an apartment are **2** as given from the numbers.

There are multiple approaches to solve this problem, first one is to user binary search for any x, we can binary search if we have the apartment between the range **x-k** to **x + k.**

Another aproach is to use two pointers ,

Sort both the arrays and then look for those pairs which have the difference greater than equal to **k** and simply count them.

Let's jump to the code implementation part of the second one.

```
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,m,k;
cin >> n >> m >> k;
vector<int>v(n), vv(m);
for(int i=0;i<n;i++)cin >> v[i];
for(int i=0;i<m;i++)cin >> b[i];
sort(v.begin(), v.end());
sort(v.begin(), v.end());
int ans = 0;
int i = 0, j = 0;
while(i < n and j < m){
if(v[i]-b[i] <= k){
ans++;
i++;
j++;
}else if(v[i] > b[j]){
j++;
}else{i++;}
}
}
```