For her next summer break, Casey is planning a trip around the world. She has picked cities, numbered to , that she would like to visit. She plans to start her trip at one of these cities, visit them in order, and end her trip by returning back to her starting point. The tickets between each pair of cities have some cost, which she intends to pay for doing contracting work in each city that have some pay.
Casey does not have any savings, so she would like to start in a city where, if she begins her trip by doing the work in that city, she will have enough money to complete her trip. That is, she will always have enough money to buy the next ticket if she starts in that city. Can you help her find such a city?
Input Specification
The input begins with an integer . The next lines each contain two integers , the cost to travel to the next city and the amount of money Casey can make in this city. represents the cost to travel from the th city to the first.
For 30% of cases, .
Output Specification
Output the smallest index of a city in which Casey can start to complete her trip, or -1
if such a city does not exist.
Sample Input 1
2
10 1
1 10
Sample Output 1
2
Explanation for Sample 1
In the first case, Casey can start in the second city, earn dollars, buy a ticket for , earn another dollar in the first city, and buy the ticket back for dollars.
Sample Input 2
3
5 5
5 5
5 4
Sample Output 2
-1
Comments