수도관

어떤 마을에 $N$개의 집이 있고 우리는 이 집들을 평면상의 점으로 표시한다.

각각의 집 $H_i$는 평면의 기준점을 기준으로 동쪽으로 $a_i$ 만큼, 북쪽으로 $b_i$ 만큼 떨어진 곳에 위치한다. 단, 집들의 $a_i$ 값은 모두 서로 다르다.

우리는 각 집에 물을 공급하기 위해서 수도관들을 매설할 것이다. 수도관은 굵은 수도관과 얇은 수도관의 두 가지가 있다. 그리고 평면의 가로 방향을 서쪽과 동쪽으로, 세로 방향을 남쪽과 북쪽으로 부르자.

굵은 수도관은 제일 서쪽인 집보다 더 서쪽인 임의의 시작점에서 시작한다. 시작점에서 출발하여 굵은 수도관들을 따라가면, 처음에 동쪽으로 가는 동서 방향 선분이 있고, 그 끝점에 이어진 남쪽 혹은 북쪽으로 가는 남북 방향 선분이 있고, 또 그 끝점에 이어진 동쪽으로 가는 동서 방향 선분이 연결된 형태로 반복되다가 임의의 끝점에서 끝나는 형태이다. 끝점은 제일 동쪽인 집보다 더 동쪽인 임의의 점이다. 굵은 수도관들을 이루는 선분들은 방금 언급한, 끝점에서 이어지는 방식 말고는 교차하거나 이어지지 않는다.

얇은 수도관은 남북 방향으로만 설치된다. 또, 얇은 수도관은 집과 굵은 수도관의 동서 방향 선분을 잇는 방식으로만 설치된다.

각 집에는 동일한 남북 거리 제한 $e$가 주어진다. ($e > 0$) 우리는 굵은 수도관의 동서 방향 선분이 모든 집에 대해 이 남북거리 제한 $e$ 이내에 지나가도록 굵은 수도관들을 설치해야 한다. 그래야만 모든 집에서, 길이 $e$ 이하인 남북 방향의 얇은 수도관을 통해서 굵은 수도관의 동서 방향 선분에서 물을 공급받을 수 있다. 즉, 남북 거리 제한 $e$는 얇은 수도관의 최대 길이를 의미한다. 이때 굵은 수도관의 남북 방향 선분에서는 물을 공급받을 수 없다. 심지어 굵은 수도관의 남북 방향 선분이 집의 위치를 지나가더라도 물을 공급받을 수 없다.

즉, 각 집 $H_i$에 대해서 굵은 수도관의 동서 방향 선분이 $H_i$를 지나가거나 또는 동서 방향 선분이 $H_i$로부터 남북 방향으로 거리 $e$ 안으로 지나가야 한다. 동서 방향 선분의 끝점이 $H_i$로부터 남북 방향으로 거리 $e$ 안에 있는 경우도 허용한다.

위에 언급한 조건으로 굵은 수도관의 동서 방향 선분의 개수가 최소가 되도록 하고 싶다.

예를 들어, 위 그림은 집이 $4$개가 있을 때의 경우이다. 그림에서 X 표시는 집을 의미하고, 굵은 선분들은 굵은 수도관, 점선은 얇은 수도관을 의미한다. 동서 방향 선분 $3$개와 남북 방향 선분 $2$개를 이용해서, 모든 집에 대해 남북 거리 제한 $e$ 이내에 굵은 수도관이 있어서 얇은 수도관으로 물을 공급받을 수 있도록 설계한 것을 알 수 있다.

입력 형식

첫 줄에 집들의 개수와 남북 거리 제한을 나타내는 두 정수 $N$과 $e$가 주어진다. ($1 \le N \le 100\,000$; $1 \le e \le 10^8$)

그다음 $N$개의 줄의 $i$번째 줄에는 집 $H_i$의 위치를 나타내는 두 정수 $a_i$와 $b_i$가 주어진다. ($1 \le i \le N$; $1 \le a_i, b_i \le 2\times 10^8$; $a_i$ 값은 서로 다름)

출력 형식

첫 줄에 모든 집에 대해 굵은 수도관의 동서 방향 선분이 남북 거리 $e$ 이하로 지나가도록 매설했을 때, 굵은 수도관의 동서 방향 선분 개수의 최솟값을 출력한다.

예제 1

5 3
2 10
4 8
5 8
7 1
9 8

3

예제 2

10 7
6 13
1 18
8 19
13 10
10 10
9 7
3 15
20 18
2 4
7 1

3

채점 방식

입력 케이스들 각각에 대해 동일한 점수가 배분된다.

해설