마감을 지키는 소포 배달

문제

한 우체국에 오늘 배달해야 할 소포가 N개 쌓여 있다. i번째 소포는 집배원이 맡아서 배달을 끝내기까지 정확히 p_i 분이 걸리고, 우체국이 문을 연 시각을 0분으로 했을 때 d_i 분까지는 배달을 마쳐야 한다. 배달이 정확히 d_i 분에 끝나는 것은 마감을 지킨 것으로 본다. 집배원은 한 명이며 0분부터 일을 시작한다. 한 번에 한 소포만 맡을 수 있고, 소포를 맡으면 중간에 멈추거나 다른 소포로 바꿀 수 없으며 p_i 분 뒤에 끝난다. 한 소포를 끝낸 뒤에는 바로 다른 소포를 맡을 수 있고, 중간에 쉬어도 되지만 쉰다고 마감이 늦춰지지는 않는다. 마감을 지키지 못할 소포는 아예 맡지 않아도 되며, 맡지 않은 소포는 다음 날 처리하므로 손해가 없다. 마감을 모두 지키면서 오늘 배달을 끝낼 수 있는 소포의 최대 개수를 구하는 프로그램을 작성하시오. 어느 소포도 마감 안에 배달할 수 없다면 0을 출력한다. 소포를 고르는 방법과 처리 순서는 자유이다.

입력

첫 줄에 소포의 수 N 이 주어진다. (1 ≤ N ≤ 200,000)
이어지는 N개의 줄에 i번째 소포의 배달 소요 시간 p_i 와 마감 시각 d_i 가 공백으로 구분되어 주어진다. (1 ≤ p_i ≤ 1,000,000, 1 ≤ d_i ≤ 1,000,000,000, 모두 정수)

출력

마감을 지켜 배달할 수 있는 소포의 최대 개수를 한 줄에 출력한다.

5
3 5
2 6
4 8
1 3
5 13

4

3
4 3
6 5
9 8

0

출처: Devin.KR 자체 제작