답답한 소

면접 대비

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

요약

왼쪽과 오른쪽 모두 거리 D 안에 키가 두 배 이상인 소가 있는 소가 몇 마리인지 셉니다.

난이도: 보통10점 중 5점
유형: 슬라이딩 윈도우, 정렬, 큐
정답자: 아직 제출이 없습니다

문제

농부 존의 소 $N$ 마리가 일직선 울타리를 따라 풀을 뜯고 있다. $i$ 번 소는 위치 $x_i$ 에 서 있고 키는 $h_i$ 다.

어떤 소는 왼쪽으로 거리 $D$ 안에 자기 키의 두 배 이상인 소가 있고 오른쪽으로도 거리 $D$ 안에 자기 키의 두 배 이상인 소가 있으면 답답함을 느낀다. 여기서 왼쪽은 위치가 $x_i - D$ 이상 $x_i$ 미만인 구간이고, 오른쪽은 $x_i$ 초과 $x_i + D$ 이하인 구간이다.

답답함을 느끼는 소는 우유를 덜 낸다. 농부 존을 도와 그런 소가 몇 마리인지 세시오.

$1 \le N \le 50000$
$1 \le x_i, h_i \le 10^9$
$1 \le D \le 10^9$

입력

첫 줄에 두 정수 $N$ 과 $D$ 가 주어진다.

다음 $N$ 개 줄에 $i$ 번 소의 위치 $x_i$ 와 키 $h_i$ 가 주어진다. 소의 위치는 모두 다르다. 입력이 위치 순으로 정렬되어 있다는 보장은 없다.

출력

답답함을 느끼는 소의 수를 한 줄에 출력한다.

힌트

예제에서는 소가 6마리이고 거리 기준 $D$ 는 4다. 첫 소는 위치 10에 키 3으로 서 있고 나머지 줄도 같은 방식으로 읽는다. 위치 5와 위치 6의 소가 답답함을 느끼므로 답은 2다.

예제1

예제 1
입력
```
6 4
10 3
6 2
5 3
9 7
3 6
11 2
```
예상 출력
```
2
```