A computer game "Village Voyage" has N villages (labeled 1 to N) at some distance from each other. The player shall start from any village S and travel through all the villages to come back to the starting village S and finish the game. At each village checkpoint, the player will find a number of energy drinks, which will help him travel further. One energy drink will give him the energy to travel one unit of distance. At any point in the journey, if he does not have the sufficient number of energy drinks, he cannot complete the tour and will lose the game. Any leftover energy gets added up to the current number of energy drinks.
At every village checkpoint, the player is provided with:
1) The number of energy drinks available in that village.
2) The distance from that village to the next village.
Write a program to help the player select a starting village S so that he is equipped with sufficient drinks to consequently win the game. If starting at multiple villages can achieve the win, then print the village with the smallest label (1 to N).
Read the input from STDIN and print the output to STDOUT. Do not write arbitrary strings anywhere in the program, as these contribute to the standard output and testcases will fail.
Constraint:
N ≥ 0
Consider that a solution exists for all the test cases provided.
Input Format:
The first line of input contains N, the number of villages.
The next N lines of input contain the number of energy drinks available at that village checkpoint, followed by the distance of the next village from the current village.
Output Format:
The output contains the starting village S.
Sample Input1:
6
3 5
5 2
6 4
6 4
5 3
4 2
Sample Output1:
2
Explanation:
There are 6 villages.
Village1 has 3 energy drinks, and distance to village2 is 5.
Village2 has 5 energy drinks, and distance to village3 is 2, and so on.
The player cannot start from the first village as the number of drinks available is 3, whereas the distance to go to the next village is 5. The player can start from the second village as 5 energy drinks gives enough energy to cover the distance between the second and the third village, which is 2. He consumes 2 energy drinks to cover the distance of 2 units and hence he saves 3 energy drinks. In the next village, he collects 6 energy drinks and the total number of energy drinks he now has is 9. He then again consumes 4 energy drinks to cover 4 units of distance. Continuing likewise, it can be seen that if he starts from the second village, he can win the game. Thus, the output is 2.
Sample Input2:
4
5 3
2 4
3 7
8 4
Sample Output2:
4
Explanation:
Here, if the player starts from the fourth village, he can win the game. Thus, the output is 4.
