Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3192
Selecting Frames

Time Limit: 1 Second      Memory Limit: 32768 KB

Given n frames of unit width, your task is to select as many frames as possible and arrange them in a line, so that none of them overlap (one enclosing another is also forbidden, but merely touching is ok).

There is a restriction, though. If you select the i-th frame, you must install a small pole at Pi, then place the i-th frame surrounding that pole (the pole is so small that it can be located on the frame border). You can place the frame anywhere, as long as the pole is inside it or on its border.


There are at most 10 test cases. Each case begins with a single integer n, the number of frames (1 <= n <= 10000). Each of the following lines contains two integers Li and Pi (1 <= Li, Pi <= 100000), the length of the i-th frame, and the position of the pole associated with that frame. No two poles will have the same position. The input ends with n = 0.


For each test case, print the maximum number of frames you can select.

Sample Input

5 9
2 17
6 10
3 11
2 16
4 13
5 6

Sample Output


Author: LIU, Rujia
Source: The 34th ACM-ICPC Asia Regional 2009 Ningbo Site NIT Cup National Invitation Contest
Submit    Status