# Codeforces858b which floor

Posted by yjjr's blog on February 6, 2018 4 minutes to read

In a building where Polycarp lives thereare equal number of flats on each floor. Unfortunately, Polycarpdon't remember how many flats are on each floor, but he remembers that theflats are numbered from 1 from lower toupper floors. That is, the first several flats are on the first floor, the nextseveral flats are on the second and so on. Polycarp don't remember the totalnumber of flats in the building, so you can consider the building to beinfinitely high (i.e. there are infinitely many floors). Note that the floorsare numbered from 1.

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

Given this information, is it possible to restore theexact 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 ofthese lines contains a pair of integers ki, fi (1 ≤ ki ≤ 100, 1 ≤ fi ≤ 100), which meansthat the flat ki is on the fi-th floor. All values ki are distinct.

It is guaranteed that the given information is notself-contradictory.

Output

Print the number of the floor in which the n-th flat islocated, 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 floorand 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 eachfloor, so we can't restore the floor for the 8-th flat.

Code

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define LL long long
using namespace std;

const int maxn=5000000;
struct node{int num,fl;}x[maxn];
inline int cmp(node a,node b){if(a.num==b.num)return a.fl<b.fl;else return a.num<b.num;}
LL q,m,flag,temp,ans,t;
int main()
{
cin>>q>>m;
rep(i,1,m){cin>>x[i].num>>x[i].fl;}
sort(x+1,x+1+m,cmp);
rep(i,1,10000){
flag=1;
rep(j,1,m){
temp=x[j].num/i;
if(x[j].num%i!=0)temp++;
if(temp!=x[j].fl)flag=0;
}
if(flag==1){
t=q/i;
if(q%i!=0)t++;
}
if(ans==0)ans=t;
if(ans!=t){cout<<"-1\n";return 0;}
}
rep(i,1,m-1){
if(x[i].num<=q&&x[i+1].num>=q&&x[i].fl==x[i+1].fl){cout<<x[i].fl<<endl;return 0;}
}
cout<<ans<<endl;
return 0;
}