Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

B. Which floor?

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputIn a building where Polycarp lives there are equal number of flats on each floor. Unfortunately, Polycarp don't remember how many flats are on each floor, but he remembers that the flats are numbered from 1 from lower to upper floors. That is, the first several flats are on the first floor, the next several flats are on the second and so on. Polycarp don't remember the total number of flats in the building, so you can consider the building to be infinitely high (i.e. there are infinitely many floors). Note that the floors are numbered from 1.

Polycarp remembers on which floors several flats are located. It is guaranteed that this information is not self-contradictory. It means that there exists a building with equal number of flats on each floor so that the flats from Polycarp's memory have the floors Polycarp remembers.

Given this information, is it possible to restore the exact floor for flat *n*?

Input

The first line contains two integers *n* and *m* (1 ≤ *n* ≤ 100, 0 ≤ *m* ≤ 100), where *n* is the number of the flat you need to restore floor for, and *m* is the number of flats in Polycarp's memory.

*m* lines follow, describing the Polycarp's memory: each of these lines contains a pair of integers *k*_{i}, *f*_{i} (1 ≤ *k*_{i} ≤ 100, 1 ≤ *f*_{i} ≤ 100), which means that the flat *k*_{i} is on the *f*_{i}-th floor. All values *k*_{i} are distinct.

It is guaranteed that the given information is not self-contradictory.

Output

Print the number of the floor in which the *n*-th flat is located, if it is possible to determine it in a unique way. Print -1 if it is not possible to uniquely restore this floor.

Examples

Input

10 3

6 2

2 1

7 3

Output

4

Input

8 4

3 1

6 2

5 2

2 1

Output

-1

Note

In the first example the 6-th flat is on the 2-nd floor, while the 7-th flat is on the 3-rd, so, the 6-th flat is the last on its floor and there are 3 flats on each floor. Thus, the 10-th flat is on the 4-th floor.

In the second example there can be 3 or 4 flats on each floor, so we can't restore the floor for the 8-th flat.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/25/2018 18:43:57 (d2).

Desktop version, switch to mobile version.

User lists

Name |
---|