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 arbitrary strings anywhere in the program, as these contribute to the standard output and testcases will fail.

Problem

Input

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

The output contains the starting village S.

Constraints

• N >= 0

Test Cases

Sample Input1:

N = 6 landmark_info = [[3, 5], [5, 2], [2, 4], [3, 5], [5, 3], [4, 2]]

Sample Output1:

2

Sample Input2:

N = 4 landmark_info = [[5, 2], [2, 4], [3, 7], [8, 4]]

Sample Output2:

4