Assistant Ranking

Time limit1sMemory limit512 MB

Summary

Given N assistants with two scores each and a tolerance K, find the maximum number of distinct ranks when a score gap above K forces a higher or equal rank.

Level: Medium7 of 10
Topics: Graph, Sorting, DFS
Solved: No attempts yet

Problem

The online retailer Amagoogsoftbook currently offers $N$ different so-called home assistants, which it wants to recommend to its customers. For this recommendation, they wish to rank all the assistants. The quality of this ranking is not very important: multiple assistants may even be assigned the same rank, but they wish to maximize the number of distinct ranks assigned, to lessen the decision fatigue of their customers.

To ensure that the ranking is not completely arbitrary, they have collected for each assistant $i$ two measurements $a_i$ and $b_i$ : the quality of the jokes the assistant can tell and how nice the compliments the assistant is able to give are (clearly these are the two most important aspects). These measurements are somewhat subjective, so they wish to ignore small differences in them. However, if for two given assistants $i$ and $j$ we have that $a_i + K < a_j$ or $b_i + K < b_j$ , the ranking of assistant $j$ must be the same or higher than the ranking of assistant $i$ . This rule may force two products to be given the same ranking, for example if assistant $i$ gives much better puns than assistant $j$ , while assistant $j$ gives the superior self-esteem boosts.

What is the maximum number of distinct ranks, taken over all possible rankings?

Input

The first line contains the integers $1 \le N \le 100\,000$ and $0 \le K \le 10^9$ : the number of assistants and the measurement difference limit. The next line contains the $N$ integers $a_1, a_2, \dots, a_N$ . The next line contains the $N$ integers $b_1, b_2, \dots, b_N$ .

All measurements are between $0$ and $10^9$ .

Output

Output a single integer: the maximum number of distinct ranks.

Examples5

Example 1
Input
```
2 10
1 12
1 13
```
Expected output
```
2
```
Example 2
Input
```
2 10
1 5
1 12
```
Expected output
```
2
```
Example 3
Input
```
2 10
1 5
1 4
```
Expected output
```
2
```
Example 4
Input
```
2 10
1 5
4 1
```
Expected output
```
2
```
Example 5
Input
```
2 10
1 12
13 1
```
Expected output
```
1
```