Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 2656
Travel Around Country

Time Limit: 10 Seconds      Memory Limit: 32768 KB

Driving a car around the country with PPMM is a one of Vivid��s Dreams. Now he is thinking about which city could be his start point, although he hasn��t got a car yet��

There are N main cities forming a loop in our country. Vivid wants to choose one city as his start point, then goes around the loop, and at last back to the city which he started from.

Of course, the car can��t finish the loop without refueling. Fortunately there always has a gas station in each city, and Vivid will take all of the oil from the gas station. You can assume the car consumes one unit of oil per one unit of distance. At the start point, the car has no oil at all, and will take all of the oil from the gas station.

Given N cities in order, with the amount of the oil it contains, and the distance to the next city. Please help Vivid to choose his start point.

Input:

There are multiple test cases. Each test case begins with a Integer N (the number of the city, 2 <= N <=10000), then N lines followed with two Integers O (the amount of oil this city has) and D (the distance to the next city).

Output:

Each test case has a line with a Integer, indicate which city could be the start point for Vivid. We consider the first city as 0, the second city as 1, and so on. If there is no such city can be found, just output impossible. If there are more than one city can be found, output the first city in the input.

Sample Input:

2
10 10
10 10
2
10 20
20 10
2
10 20
10 20

Sample Output:

0
1
impossible



Author: JIN Tianpeng
Source: ZOJ Monthly, February 2006
Submit    Status