B. Какой этаж?
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В доме Поликарпа на каждом этаже одинаковое количество квартир. К сожалению, Поликарп не помнит, сколько именно квартир на каждом этаже, зато он помнит, что квартиры пронумерованы от 1 снизу вверх. Таким образом, в нумерации сначала идут квартиры первого этажа, затем второго и так далее. Поликарп не помнит точное количество квартир в доме, вы можете считать дом бесконечно высоким (то есть содержащим бесконечное количество квартир). Обратите внимание, этажи нумеруются с 1.

Про некоторые квартиры Поликарп помнит, на каких этажах они расположены. Гарантируется, что воспоминания Поликарпа непротиворечивы. То есть существует дом с одинаковым количеством квартир на каждом этаже, такой что квартиры из воспоминания Поликарпа имеют те этажи, которые он запомнил.

Может ли он на основании этой информации указать точный этаж для квартиры n?

Входные данные

В первой строке записаны два целых числа n и m (1 ≤ n ≤ 100, 0 ≤ m ≤ 100), где n — номер квартиры, этаж которой надо определить, и m — количество квартир в воспоминании Поликарпа.

Далее следуют m строк, которые описывают воспоминание Поликарпа: каждая из этих строк содержит пару чисел ki, fi (1 ≤ ki ≤ 100, 1 ≤ fi ≤ 100), которая означает, что квартира ki находится на этаже fi. Все значения ki — различны.

Гарантируется, что воспоминания Поликарпа непротиворечивы.

Выходные данные

Выведите номер этажа, на котором расположена квартира n, если его номер однозначно определяется по воспоминанию Поликарпа. Выведите -1, если однозначно восстановить номер этажа невозможно.

Примеры
Входные данные
10 3
6 2
2 1
7 3
Выходные данные
4
Входные данные
8 4
3 1
6 2
5 2
2 1
Выходные данные
-1
Примечание

В первом примере 6-я квартира находится на 2-м этаже, а 7-я уже на 3-м, следовательно, 6-я квартира последняя на своём этаже, а всего на этаже 3 квартиры. Таким образом, 10-я квартира находится на 4-м этаже.

Во втором примере на каждом этаже может быть 3 или 4 квартиры, поэтому мы не можем узнать, на каком этаже находится 8-я квартира.