LCC/Moose '19 Contest 2 S3 - Round Trip

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem types

For her next summer break, Casey is planning a trip around the world. She has picked N cities, numbered 1 to N, 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 N (1 \le N \le 10^5). The next N lines each contain two integers C_i, P_i (0 \le C_i, P_i \le 1,000), the cost to travel to the next city and the amount of money Casey can make in this city. C_N represents the cost to travel from the Nth city to the first.

For 30% of cases, N \le 1000.

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 10 dollars, buy a ticket for 1, earn another dollar in the first city, and buy the ticket back for 10 dollars.

Sample Input 2

3
5 5
5 5
5 4

Sample Output 2

-1

Comments

There are no comments at the moment.