Philip J. Fry Problem |
Nibbler, Leela's stupid pet, is also a member of the crew and a critical element to succeed in the mission. Nibbler's feces, which it expels every now and then, consist of spheres of dark matter that can be used to increase the speed of the spaceship. In fact, a sphere used during a trip halves its duration. Bender's role in the mission is to pick up the heavy spheres and put them in the reactor of the spaceship. However, he will never put two spheres during the same trip: the accumulation of dark matter is extremely dangerous and may destroy the spaceship.
In each trip of the mission, Nibbler expels a certain number of dark matter spheres that can be used to decrease the duration
of any of the upcoming trips. In other words, a sphere of dark matter produced during the trip can be used to duplicate the
speed of the spaceship in one of the trips , with
i < j n.
Fry is responsible for planning how to use the spheres to reduce the total travel time. Your task is to help Fry in determining
what is the minimum duration of the mission if he uses Nibbler's spheres cleverly.
The input consists of several test cases. The first line of each case contains an integer n indicating the number of trips ( 1 n 100). Then, n lines follow describing each of the trips , , ..., : each line contains two integers ti and bi separated by blanks, where ti ( 2 ti 1000) indicates the duration in minutes specified by Professor Farnsworth for the trip (ti is always even) and bi ( 0 bi n) indicates the number of dark matter spheres that Nibbler will expel during the trip . The last test case is followed by a line containing a single `0'.
For each test case, print a line with an integer number indicating the minimum time required to complete the mission.
2 24 1 10 0 2 10 1 24 0 3 10 0 24 0 38 0 3 10 1 24 0 14 0 3 10 1 24 0 38 0 3 10 1 24 1 38 0 3 10 3 24 0 38 1 0
29 22 72 36 53 41 41