Какой этаж?

[foxy15131]

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

Алексей поселился в апартаменты с номером n, но совсем забыл спросить при регистрации, на каком этаже находится его номер. Зато при этом он подслушал разговоры нескольких других постояльцев, и запомнил, в каких номерах и на каких этажах они проживают. Гарантируется, что воспоминания Алексея непротиворечивы. То есть существует гостиница с одинаковым количеством номеров на каждом этаже, такая, что номера из воспоминания Алексея имеют те этажи, которые он запомнил.

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



Замечание

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

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

Формат входных данных
В первой строке записаны два целых числа 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

[foxy15131]

это очень срочно

[foxy15131]

На языке java
Благодарю за помощь

[foxy15131]

Я не понимаю, как это реализовать.