Which floor?

题意 在Polycarp住的一栋建筑里，每一层有一些相等数量的公寓。不幸的是，Polycarp不记得在一层上有多少公寓了，但是他记得那些公寓是从1开始编号的，编号从低层到高层。那意味着，最开始的几个公寓在第一层，之后的几个公寓在第二层，以此类推。Polycarp不记得建筑里公寓的总数量，所以你可以将这栋建筑看为无限高（即有无限层）。注意楼层是从1开始编号的。 Polycarp记得几个公寓分别在哪几层。保证这些信息不会自我矛盾。（还有句话） 给你这些信息，你可以求出有n个公寓的建筑的确切层数吗？ 输入格式： 第一行包含两个整数n，m。$(1<=n<=100,0<=m<=100)$ 。n是你重建的建筑的公寓数，而m是Polycarp记得的公寓数。 接下来的m行，每一行包含一对整数$k_{i}$ ,$f_{i}$ 。$(1<=k_{i}<=100,1<=f_{i}<=100)$ ，表示公寓$k_{i}$ 在第$f_{i}$ 层。所有的$k_{i}$ 都是不同的。 输出格式： 如果能确定唯一的层数，输出有n个公寓的建筑的层数。 如果不能确定，输出-1。 贡献者：Fowany

In 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 $ ?

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.

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.

10 3
6 2
2 1
7 3

4

8 4
3 1
6 2
5 2
2 1

-1

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.