提示: 欢迎访问OurACM平台。
Problem 1784 Selecting Frames

Accept: 16    Submit: 48
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem 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

2009 NIT Cup National Invitation Contest

Submit  Back  Status  Discuss