Задача C. Carriage inspectors

Автор:M. Sporyshev, I. Tuphanov   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N, M ≤ 200000

1 ≤ Ai ≤ N

 − 106 ≤ Vi ≤ 106, Vi ≠ 0

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

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

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 1
2 1
1
2
5 2
5 -2
1 1
2

0.093s 0.022s 15