직선 위의 클리크

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

요약

직선 위의 점 n개에 가중치가 주어지고 두 점의 가중치 합이 거리 이하일 때 인접하다고 할 때, 가장 큰 클리크의 크기를 구한다.

난이도: 어려움10점 중 9점
유형: 동적 계획법, 정렬, 이분 탐색, 그리디
정답자: 아직 제출이 없습니다

문제

클리크 문제(clique problem)는 NP-complete 문제로 잘 알려져 있다. 정의는 간단하다. 무향 그래프 $G$ 에서 정점의 부분집합 $C$ 를 고른다. $C$ 에 속한 모든 정점 쌍이 서로 간선으로 이어져 있으면, 즉 $C$ 가 완전그래프를 이루면 $C$ 를 클리크라고 부른다. 가장 큰 클리크의 크기를 구하는 것이 클리크 문제다.

$x$ 축 위에 좌표가 서로 다른 점 $n$ 개가 있다. $i$ 번 점의 좌표는 $x_i$ , 무게는 $w_i$ 다. 이 점들로 그래프를 만든다. 서로 다른 두 점 $i$ 와 $j$ 는 $w_i + w_j \le |x_i - x_j|$ 를 만족할 때만 간선으로 이어진다.

이렇게 만든 그래프에서 가장 큰 클리크의 크기를 구하라.

입력

첫째 줄에 점의 개수 $n$ 이 주어진다. ( $1 \le n \le 200000$ )

다음 $n$ 개의 줄에 각각 두 정수 $x_i$ 와 $w_i$ 가 주어진다. ( $1 \le x_i, w_i \le 10^9$ )

모든 $x_i$ 는 서로 다르다.

출력

첫째 줄에 가장 큰 클리크의 크기를 출력한다.

예제7

예제 1
입력
```
4
2 2
3 1
6 2
1 1
```
예상 출력
```
3
```
예제 2
입력
```
1
1000000000 1000000000
```
예상 출력
```
1
```
예제 3
입력
```
2
1 1
3 1
```
예상 출력
```
2
```
예제 4
입력
```
2
1 2
3 1
```
예상 출력
```
1
```
예제 5
입력
```
5
10 100
20 100
30 100
40 100
50 100
```
예상 출력
```
1
```
예제 6
입력
```
6
1 1
2 5
3 1
5 1
7 1
9 1
```
예상 출력
```
5
```
예제 7
입력
```
5
5 4
6 1
7 1
8 1
100 1
```
예상 출력
```
3
```