광고 2

면접 대비

시간 제한2초메모리 제한1024 MB

요약

주민마다 좌표와 영향력이 주어질 때, 모든 주민이 책을 받게 하려고 기증해야 하는 최소 인원을 구합니다.

난이도: 보통10점 중 6점
유형: 구간, 정렬, 그리디
정답자: 아직 제출이 없습니다

문제

JOI 왕국에는 1번부터 $N$ 번까지 $N$ 명의 주민이 살고 있다. 주민 $i$ ( $1 \le i \le N$ )는 실수선 위의 좌표 $X_i$ 에 살며, 영향력은 $E_i$ 이다. 같은 좌표에 여러 명이 살 수도 있다. 영향력이 큰 주민은 광고 효과가 크지만, 책을 살 때는 신중하다.

리에가 정보학 책을 출판했다. 많은 사람이 책을 사도록, 리에는 일부 주민에게 책을 무상으로 줄 수 있다. 주민 $i$ 에게 책을 주면 주민 $i$ 는 책을 받는다. 그다음, 아직 책을 받지 못한 주민 중 아래 조건을 만족하는 주민 $j$ ( $1 \le j \le N$ )는 책을 사서 받는다.

$|X_i - X_j| \le E_i - E_j$

모든 주민이 책을 읽으면 정보올림피아드가 크게 알려질 것이다. 모든 주민이 책을 받도록 할 때, 책을 무상으로 줘야 하는 주민 수의 최솟값을 구하는 프로그램을 작성하라.

입력

표준 입력에서 다음 데이터를 읽는다.

N
X_1 E_1
X_2 E_2
\vdots
X_N E_N

출력

표준 출력에 한 줄로, 리에의 책을 무상으로 줘야 하는 주민 수의 최솟값을 출력한다.

제한

$1 \le N \le 500\,000$ .
$1 \le X_i \le 10^9$ ( $1 \le i \le N$ ).
$1 \le E_i \le 10^9$ ( $1 \le i \le N$ ).
주어지는 값은 모두 정수이다.

예제3

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

예제 3

입력

10
31447678 204745778
430226982 292647686
327782937 367372305
843320852 822224390
687565054 738216211
970840050 766211141
563662348 742939240
103739645 854320982
294864525 601612333
375952316 469655019

예상 출력