품평회 행사 참석

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

요약

N개의 구간이 주어질 때, 서로 겹치지 않게 참석할 수 있는 최대 구간 수를 구한다.

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

문제

농부 존이 품평회에 다시 왔다. 이곳에서는 콘서트, 로데오, 요리 시연 같은 특별 행사가 $N$ 개 열리고, 존은 그중 최대한 많은 행사에 참석하려고 한다.

존은 자전거를 빌렸기 때문에 한 행사장에서 다음 행사장으로 이동하는 데 시간이 전혀 걸리지 않는다.

$i$ 번째 행사는 시각 $T_i$ 에 시작해서 $L_i$ 만큼 진행되므로 시각 $T_i + L_i$ 에 끝난다. 존은 행사를 중간에 떠나지 않으므로, 어떤 행사에 참석하려면 시작부터 끝까지 자리를 지켜야 한다. 한 행사가 끝나는 시각과 다른 행사가 시작하는 시각이 같으면 두 행사 모두 참석할 수 있다.

존이 참석할 수 있는 행사 수의 최댓값을 구하시오.

입력

첫째 줄에 행사의 개수 $N$ 이 주어진다. ( $1 \le N \le 10000$ )

둘째 줄부터 $N$ 개 줄에 걸쳐 한 행사의 시작 시각 $T$ 와 진행 시간 $L$ 이 공백으로 구분되어 주어진다. ( $1 \le T \le 100000$ , $1 \le L \le 100000$ )

출력

첫째 줄에 존이 참석할 수 있는 행사 수의 최댓값을 출력한다.

예제5

예제 1
입력
```
7
1 6
8 6
14 5
19 2
1 8
18 3
10 6
```
예상 출력
```
4
```
예제 2
입력
```
1
1 1
```
예상 출력
```
1
```

예제 3

입력

예상 출력

예제 4
입력
```
4
1 3
4 2
6 5
11 1
```
예상 출력
```
4
```
예제 5
입력
```
5
1 20
1 4
5 4
9 4
13 4
```
예상 출력
```
4
```