배

면접 대비

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

요약

각 배는 정해진 길이와 링 위치를 가지며, 링이 배 위에 오도록 묶을 때 배끼리 겹치지 않고 최대 몇 척을 묶을 수 있는지 구한다.

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

문제

마법사들이 아글라르곤드 마법학교의 대회에 참가한다. 여러 이동 수단 중 배를 타고 올 수도 있다. 주최측은 참가자마다 고리를 하나씩 배정해 두었고, 각자는 자신에게 배정된 고리에 배를 묶을 수 있다. 모든 마법사는 자기 배의 길이를 주최측에 보냈다. 배를 묶을 때 고리는 배의 길이 위에 있어야 하며, 배의 양 끝점도 포함된다. 배의 끝은 서로 닿을 수 있지만 배끼리 겹칠 수는 없다(그림 참조). 이 제약 때문에 모든 배를 동시에 묶지 못할 수도 있다. 마법사 대회 조직위원회는 배정된 고리에 동시에 묶을 수 있는 배의 최대 개수를 구하는 프로그램을 작성해 달라고 요청했다.

허용됨	허용되지 않음

입력

첫 줄에는 마법사의 수 N이 주어진다(1 ≤ N ≤ 10000). 다음 N개 줄에는 배의 길이 li와 학교 건물부터 강둑을 따라 잰, 배정된 고리의 위치 pi가 공백으로 구분되어 주어진다(1 ≤ li, pi ≤ 100000, 1 ≤ i ≤ N). 두 고리가 같은 위치에 있는 경우는 없다.

출력

한 줄에 묶을 수 있는 배의 최대 개수를 출력한다.

예제1

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