Selecting Frames

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 L_i and P_i(1 <= L_i, P_i <= 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.

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

5

2009 “NIT Cup” National Invitational Contest