Задача C. Carriage inspectors ≡

Условие

Программист Вася каждый день ездит на работу на электричке. Сегодня Вася как обычно пришёл на станцию, но забыл с собой кошелёк! Домой возвращаться уже нет времени. Вася решил сесть в поезд без билета, так что попасться на глаза контролёру он не хочет.

В поезде N вагонов и M контролёров. На своё счастье, Вася уже давно ездит на одной и той же электричке и знает A_i — номера вагонов, где будут находиться контролёры на момент его захода в поезд. Также он знает направления движения каждого контролёра (к первому вагону или к последнему) и их скорости V_i — количество вагонов в час, которое проходит i-й контролёр. Таким образом, через каждые 1 / V_i часов контролёр переходит в следующий вагон в своём направлении. Контролёр останавливается если дальше в его направлении нет вагонов.

Ехать Васе очень долго, поэтому он хочет выбрать вагон, в котором он сможет просидеть дольше всего до момента как в его вагоне появится контролёр. Помогите ему в этом.

Формат входного файла

Первая строка входного файла содержит целые числа N и M — количество вагонов и количество контролёров соответственно.

Далее следует M строк, i-я строка содержит два целых числа A_i, V_i — вагон, в котором находится соответствующий контролёр в момент захода Васи в поезд и его скорость движения. V_i отрицательна, если контролёр движется в сторону вагона с меньшим номером, и положительна в обратном случае.

Формат выходного файла

В выходной файл выведите номер вагона, в котором должен сесть Вася. Вагоны нумеруются с единицы. Если решений несколько, выведите любое из них.

Ограничения

1 ≤ N, M ≤ 200000

1 ≤ A_i ≤ N

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

Пояснение к примерам

В первом примере Вася может зайти в первый вагон и ехать сколько угодно.

Во втором примере вагоны 1 и 5 содержат контролёров в момент времени 0. Через 0.5 часа первый контролёр заходит в вагон 4. Через 1 час от начала поездки контролёр 1 заходит в вагон 2, а контролёр 2 заходит в вагон 3. Таким образом, как 2, так и 3 является правильным ответом.

Примеры тестов

3 1
2 1

1

5 2
5 -2
1 1

2