Charley's Bike Ride

Problem Background

Special for beginners, ^_^

Problem Description

The start and the finish are $4500$ meters apart. Charley needs to ride from the start to the finish. He has a habit: he needs company along the way — someone riding with him at the same speed. When he meets someone riding faster, he speeds up to follow that faster person. Given the speeds and departure times of all people going the same way as Charley, compute how long Charley takes to finish the $4500$ meters by following people this way. If the result is not an integer, round it up.

Input Format

There are several test cases. Each case starts with an integer $n\ (1\le n\le 10000)$; $n=0$ indicates the end of input. Then $n$ lines follow, each with two values: speed $v$ and departure time $t$. If $t<0$, the companion started earlier.

Output Format

For each test case, output one line containing one number: the fastest arrival time.

Sample Input

4
20 0
25 -155
27 190
30 240
2
21 0
22 34
0

Sample Output

780
771

Constraints

Time limit 1s, memory limit 1024KiB for each test case.