J. Battleship
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Petya and Vasya got bored of playing with pebbles, and they decided to invent their own game. The Battleship was taken as a basis and was improved.

The new game is played on a $$$ 1 \times n $$$ checkered field. The cells of the field are numbered from 1 to $$$ n $$$ from left to right.

Petya hides a single ship with a length of $$$ k $$$ decks on the field.

Vasya tries to find the ship by guessing the numbers $$$ t $$$ and telling them to Petya. In response to the reported number $$$ t $$$, Petya calculates the number $$$ r $$$ – how many times the ship would have been hit if the cells $$$ t, 2t, 3t, ..., r \times t, ... $$$ had been shot. The results of the attempts are recorded in the protocol. Vasya can make $$$ c $$$ attempts and wins if he accurately determines the position of Petya's ship.

Write a program that, according to the protocol of the game finds the position of the ship, if such a position exists.

Input

The first line contains three integers $$$n$$$, $$$k$$$ ($$$1 \lt n \leq 1000, 0 \lt k \lt n$$$) and $$$c$$$ ($$$0\leq c \leq 100$$$). This is followed by $$$c$$$ lines containing pairs of numbers $$$t_i$$$ (step of the $$$i$$$th attempt, $$$0 \lt t_i \lt n$$$) and $$$r_i$$$ (result of the $$$i$$$th attempt, $$$0\leq r_i \leq k$$$).

Output

In a single line, print a number – the position of the ship, given by the number of its leftmost cell. If the position does not exist, print -1. If there are several valid positions, then print the leftmost one.

Examples
Input
16 5 3
2 3
3 1
5 1
Output
4
Input
16 5 3
2 3
3 1
15 1
Output
-1
Input
16 5 3
2 3
3 1
14 1
Output
10