어시스턴트 순위 매기기

시간 제한1초메모리 제한512 MB

요약

어시스턴트 N개마다 두 점수 a, b와 허용 차이 K가 주어집니다. 점수 차이가 K를 넘으면 순위 제약이 생기는데, 이를 지키면서 만들 수 있는 서로 다른 순위의 최대 개수를 구합니다.

난이도: 보통10점 중 7점
유형: 그래프, 정렬, DFS
정답자: 아직 제출이 없습니다

문제

온라인 소매업체 Amagoogsoftbook은 현재 고객에게 추천하려는 이른바 「가정용 어시스턴트」를 서로 다른 $N$ 종 판매한다. 업체는 이 추천을 위해 모든 어시스턴트의 순위를 매기려 한다. 순위의 정밀도는 그다지 중요하지 않다. 여러 어시스턴트에 같은 순위를 줄 수도 있지만, 고객의 결정 피로를 줄이기 위해 부여되는 서로 다른 순위의 개수를 최대화하려 한다.

순위가 완전히 임의로 정해지지 않도록, 어시스턴트 $i$ 마다 두 측정값 $a_i$ 와 $b_i$ 를 모았다. 각각 그 어시스턴트가 하는 농담의 수준과 해주는 칭찬의 훌륭함이며, 이 둘이 가장 중요한 요소다. 측정값은 주관적인 면이 있으므로 작은 차이는 무시하려 한다. 그러나 두 어시스턴트 $i$ , $j$ 에 대해 $a_i + K < a_j$ 또는 $b_i + K < b_j$ 이면, 어시스턴트 $j$ 의 순위는 어시스턴트 $i$ 와 같거나 그보다 높아야 한다. 이 규칙 때문에 두 제품이 같은 순위를 받아야 할 수도 있다. 예를 들어 어시스턴트 $i$ 의 말장난이 $j$ 보다 훨씬 낫고, $j$ 가 자존감을 높이는 칭찬을 더 잘하는 경우가 그렇다.

가능한 모든 순위 중에서 서로 다른 순위의 최대 개수는 얼마인가?

입력

첫 줄에 정수 $1 \le N \le 100\,000$ 과 $0 \le K \le 10^9$ 가 주어진다. 이는 어시스턴트의 수와 측정값 차이의 한계다. 다음 줄에는 $N$ 개의 정수 $a_1, a_2, \dots, a_N$ 이, 그다음 줄에는 $N$ 개의 정수 $b_1, b_2, \dots, b_N$ 이 주어진다.

모든 측정값은 $0$ 이상 $10^9$ 이하이다.

출력

서로 다른 순위의 최대 개수를 나타내는 정수 하나를 출력한다.

예제5

예제 1
입력
```
2 10
1 12
1 13
```
예상 출력
```
2
```
예제 2
입력
```
2 10
1 5
1 12
```
예상 출력
```
2
```
예제 3
입력
```
2 10
1 5
1 4
```
예상 출력
```
2
```
예제 4
입력
```
2 10
1 5
4 1
```
예상 출력
```
2
```
예제 5
입력
```
2 10
1 12
13 1
```
예상 출력
```
1
```