Selecting Frames

Time Limit: 1000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 3249
64-bit integer IO format: %I64d      Java class name: Main

Description

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.

Input

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.

Output

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

Sample Input

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

Sample Output

5

Source

Language: 
Theme: 
Share Code? 

Powered by NB231 | Current Style: .