Задача 4. Безопасное место ≡

Условие

я В некоторой 2D-игре про монстров и волшебников вы нашли артефакт сотого уровня. И к сожалению вы не сотого уровня, поэтому не можете взять артефакт с собой на следующую локацию, но можете передвинуть его на какую-либо клетку этого уровня.

На поле N клеток и M монстров. Вы знаете расположение, направление и скорость движения всех монстров. Их интеллект оставляет желать лучшего, так как они всегда движутся в одном направлении с постоянной скоростью 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

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

В первом примере артефакт можно поставить в 3 клетку и оно там будет в безопасности сколько угодно времени.

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

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

3 1
2 -1

3

5 2
1 2
5 -1

3