Problem C. Carriage inspectors ≡

Statement

Programmer Vasya commutes to work by train every day. Vasya came to the train station today as usual, but forgot his wallet! There is no time to get back. Vasya decided to take the train without buying a ticket. Obviously, he wouldn't be happy to meet an inspector now.

The train consists of N carriages served by M inspectors. Luckily, Vasya always takes this train and knows A_i — numbers of carriages where inspectors are located at the moment he enters the train. He also knows the direction (toward the first or toward the last carriage) of each inspector and his (or her) speed V_i — the number of carriages that the inspector passes per hour. Thus every 1 / V_i hours the inspector moves to the next carriage in his (or her) direction. The inspector stops if there is no next carriage in that direction.

The trip to work is long, so Vasya wants to pick a carriage where he could stay as long as possible until the moment when an inspector shows up in his carriage. Help Vasya with this.

Input file format

First string of the input contains integers N and M — the number of carriages and the number of inspectors accordingly.

Then M lines follow, i-th line contains integers A_i, V_i — carriage number where the inspector i is located when Vasya gets on the train, and his (or her) speed. V_i is negative if the inspector is moving toward the first carriage, and positive otherwise.

Output file format

Output the number of carriage which Vasya should get in to. Carriages are numbered from 1. If there are multiple solutions, output any of them.

Constraints

1 ≤ N, M ≤ 200000

1 ≤ A_i ≤ N

 − 10⁶ ≤ V_i ≤ 10⁶, V_i ≠ 0

Note on samples

In the first sample input Vasya can stay in the carriage number 1 as long as he wants.

In the seconds sample input there are inspectors in carriages 1 and 5 at time 0. After 0.5 hours inspector 1 enters carriage 4. After 1 hour from the beginning of the ride, inspector 1 enters carriage 2, while inspector 2 enters carriage 3. Thus, both 2 and 3 are correct answers.

Sample tests

3 1
2 1

1

5 2
5 -2
1 1

2