Пете и Васе наскучило играть в камешки, и они решили изобрести собственную игру. За основу был взят морской бой и усовершенствован.
Новая игра ведется на клетчатом поле размером $$$ 1 \times n $$$. Клетки поля пронумерованы числами от 1 до $$$ n $$$ слева направо.
Петя прячет на поле единственный корабль длиной $$$ k $$$ палуб.
Вася пытается найти корабль, загадывая числа $$$ t $$$ и сообщая их Пете. В ответ на сообщенное число $$$ t $$$ Петя вычисляет число $$$ r $$$ – сколько раз бы произошло попадание в корабль, если бы стреляли по клеткам $$$ t, 2t, 3t, ..., r \times t, ... $$$. Результаты попыток записываются в протокол. Вася может сделать $$$ c $$$ попыток и выигрывает, если точно определяет положение корабля Пети.
Напишите программу, которая по протоколу игры найдет позицию корабля, если такая позиция существует.
Первая строка содержит три целых числа $$$ n $$$, $$$ k $$$ ($$$ 1 \lt n \leq 1000, 0 \lt k \lt n $$$) и $$$ c $$$ ($$$ 0 \leq c \leq 100 $$$). Далее следуют $$$ c $$$ строк, содержащих пары чисел $$$ t_i $$$ (шаг $$$i$$$-й попытки, $$$ 0 \lt t_i \lt n $$$) и $$$ r_i $$$ (результат $$$i$$$-й попытки, $$$0\leq r_i \leq k$$$).
В единственной строке выведите число – позицию корабля, заданную номером его самой левой клетки. Если позиции не существует, выведите -1. Если допустимых позиций несколько, то выведите самую левую из них.
16 5 32 33 15 1
4
16 5 32 33 115 1
-1
16 5 32 33 114 1
10
