Problem: Posters

Want to try solving this problem? You can submit your code online if you log in or register.

Posters

Input File: postin.txt
Output File: postout.txt
Time Limit: 1 second

You run a poster advertisement company. Your company is quite small: all it owns is a rectangular wall in the city. Advertisers pay to put up their poster on your wall at some time at some position along the wall. These posters may have different widths, but are all exactly the same height as the wall. When a poster is put up, it may cover some of the posters already on the wall.

You have a log of every single poster put on your wall: their distance from the left end, their width, and the time they were put up.

Since people always walk from the left to the right of your wall, and we all know advertisement posters are only effective when they are completely uncovered (e.g. a burger picture will only be mouthwatering if you see the whole burger), you would like to determine the leftmost fully visible poster.

Input

The first line will contain a single integer N, the number of posters that have been put up. The next N lines will contain descriptions of the posters in chronological order (from earliest to most recent). The ith of these lines will contain two integers x_i and w_i, which indicate the distance from the left end and the width of poster i respectively. (All units are in metres.)

Output

Output should consist of a single integer: the index i of the leftmost, completely visible poster (where the index of the first poster is 1).

Sample Input 1

Sample Input 2

Sample Output 1

Sample Output 2

Explanation

In the first sample case, the first and second posters are both partially covered by the third poster. While the fourth poster is completely visible, it is further to the right of the third poster and does not overlap it, so the third poster is the leftmost completely visible poster.

In the second sample case, the first poster is partially covered by the second, the second is partially covered by the seventh, the third and fourth are covered by the fifth, and the sixth is partially covered by the seventh. The seventh poster is the only completely visible poster.

Constraints

To evaluate your solution, the judges will run your program against several different input files. All of these files will adhere to the following bounds:

1 ≤ x_i ≤ 1,000,000
1 ≤ w_i ≤ 10,000
1 ≤ N ≤ 100,000

As some of the test cases will be quite large, you may need to think about how well your solution scales for larger input values. However, not all the cases will be large. In particular:

For 60% of cases, 1 ≤ N ≤ 200.

Scoring

The score for each input scenario will be 100% if the correct answer is written to the output file, and 0% otherwise.