Filling Time -- Problem M (50 points)


A truck makes deliveries to N successive towns along a single road, where N can be up to 20. For each town the driver knows the amount of fuel available at that town and the amount of fuel required to reach the next town. He wants to minimise the number of stops he must make to refuel, so he needs to calculate the best places to fill and how much fuel to get at each stop. Assuming that the truck initially has an empty tank, and its tank capacity can be made as large as necessary, you must work out the minimum possible number of refueling stops.

The input file for this problem is called PROBLEMM.DAT. Each line of the file contains two integers, the first being the amount of fuel available at a town and the second being the amount of fuel needed to reach the next town. Both of these numbers will be positive and no more than l 00. The first line gives the information for the starting town; the remaining (non-zero) lines give the information for the first N-1 towns. The file is terminated by a line containing two zeroes.

Output, which must be written to standard output (the screen), must be the least number of refuelling stops necessary, left justified. Note that, since the truck starts empty, the answer is at least l. You should assume a solution always exists.

Example Input

37 10
11 12
25 13
20 4
12 8
27 15
0 0

Example Output

2