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? 


-----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.

Difficulty: interview

Starter code:

Solutions:
def floo(num, k):
	return (num - 1) // k + 1

def main():
	n, m = map(int, input().split())
	low = 1
	high = 10**9

	if (m == 0):
		if (n == 1):
			print(1)
		else:
			print(-1)
		return

	for i in range(m):
		k, f = map(int, input().split())
		low = max(low, (k + f - 1) // f)
		if (f > 1):
			high = min(high, (k - 1) // (f - 1))
	if (floo(n, low) == floo(n, high)):
		print(floo(n, low))
	else:
		print(-1)



main()

n, m = [int(x) for x in input().split()]
data = []
for i in range(m):
    k, f = [int(x) for x in input().split()]
    data.append((k - 1, f - 1))
ans = set()
#tmp = []
for x in range(1, 101):
    for elem in data:
        if elem[0] // x != elem[1]:
            break
    else:
        ans.add((n - 1) // x + 1)
        #tmp.append((n - 1) // x + 1)
if len(ans) == 1:
    print(ans.pop())
else:
    print(-1)

n, m = map(int, input().split())
a = []
for i in range(m):
    k, f = map(int, input().split())
    a.append((k, f))
fl = []
ps = 0
val = -1
for i in range(1, 1000):
    flag = 1
    for j in range(m):
        if (a[j][0] - 1) // i != a[j][1] - 1:
            flag = 0
    if (flag):
        ps += 1
        fl.append(i)
ans = []
for i in range(len(fl)):
    ans.append(((n - 1) // fl[i]) + 1)
if not len(ans):
    print(-1)
else:
    tmp = ans[0]
    flag = 1
    for i in range(len(ans)):
        if ans[i] != tmp:
            flag = 0
    if not flag:
        print(-1)
    else:
        print(ans[0])

def rec(i):
    nonlocal a
    return i
import sys
from collections import Counter
sys.setrecursionlimit(10**6)
#n=int(input())
n,m=list(map(int,input().split()))
a=[[] for i in range(100)]
b=[i for i in range(1,101)]
for i in range(m):
    x,y=list(map(int,input().split()))
    z=b.copy()
    for i0 in z:
        if not(((x-1)>=(y-1)*i0)and((x-1)<y*i0)):
            b.remove(i0)

a=set()
for i0 in b:
    a.add((n-1)//i0)
if len(a)==1:
    print(a.pop()+1)
else:
    print(-1)


a,b = list(map(int,input().split()))
mini = 1
maxi = 10000
for i in range(b):
    x,y = list(map(int,input().split()))
    if y==1:
        mini = max(mini,x)
    else:
        mx = (x-1)//(y-1) 
        mn=(x-1)//y+1
        if mn*y>=x:
            mini = max(mini,mn)
        else:
            mini = max(mini,mn+1)
        if mx*y>=x:
            maxi = min(maxi,mx)
if (a-1)//maxi==(a-1)//mini:
    print((a-1)//maxi+1)
else:
    print(-1)


n, m = list(map(int, input().split()))
#memory = [[] * 100 for i in range(100)]
memory = []
for i in range(m):
    a, b = list(map(int, input().split()))
    memory.append((a, b))
#memory.sort()
#count = 0
ans = -1
gl_flag = 1
for flat in range(1, 101):
    flag = 1
    for i in range(m):
        if not (memory[i][0] <= memory[i][1] * flat and memory[i][0] > (memory[i][1] - 1) * flat):
            flag = 0
            break
    if (flag == 1):
        #count += 1
        ans1 = (n - 1) // flat + 1
        if (ans != -1 and ans1 != ans):
            gl_flag = 0
            break
        else:
            ans = ans1 
if (gl_flag == 0):
    print(-1)
else:
    print(ans)


import math
n,m=map(int,input().split())
znach=range(1,200)
for i in range(m):
    k,f=map(int,input().split())
    if f==1:
        a=range(math.ceil(k/f),200)
    else:
        niz=math.ceil(k/f)
        verh=math.floor((k-1)/(f-1))
        a=range(niz,verh+1)
    znach=list(set(a)&set(znach))
if len(znach)==1:
    if n%znach[0]==0:
        print(n//znach[0])
    else:
        print(n//znach[0]+1)
else:
    a=[]
    for i in range(len(znach)):
        if n%znach[i]==0:
            a.append(n//znach[i])
        else:
            a.append(n//znach[i]+1)
    a=list(set(a))
    if len(a)>1:
        print(-1)
    else:
        print(a[0])

n, m = list(map(int, input().split()))
d = []

count_of_good = 0
good_on_level = []

for i in range(m):
    a, b = list(map(int, input().split()))
    d.append((a, b))

for on_level in range(1, 101):
    good = True
    for el in d:
        etaj = el[1]
        kv = el[0]
        if not ((etaj - 1) * on_level < kv <= etaj * on_level):
            good = False
            break
    if good:
        count_of_good += 1
        good_on_level.append(on_level)

ans = []

for i in good_on_level:
    if n % i == 0:
        ans.append(n // i)
    else:
        ans.append(n // i + 1)

if len(ans) == 1:
    print(ans[0])
    return

for i in range(1, len(ans)):
    if ans[i - 1] != ans[i]:
        print('-1')
        return

print(ans[0])


n, m = [int(i) for i in input().split()]
mn = 10 ** 5
mx = 1
n -= 1
for i in range(m):
    x, y = [int(i) for i in input().split()]
    x -= 1
    y -= 1
    if y != 0:
        mn = min(mn, x // y)
    mx = max(mx, [(x + y) // (y + 1), x // (y + 1) + 1][x % (y + 1) == 0])
a = n // mx
for i in range(mx + 1, mn + 1):
    if a != n // i:
        print(-1)
        return
print(a + 1)

m, n = map(int, input().split())
canbe = []
for i in range(0, n):
    numb, et = map(int, input().split())
    can = []
    for j in range(1, 101):
        if j * et >= numb and j * (et - 1) < numb:
            can += [j]
    canbe += [can]
    can = []
canbeat = []
for i in range(1, 101):
    est = 0
    for el in canbe:
        if i in el:
            est += 1
    if est == n:
        canbeat += [i]
ans = []
for element in canbeat:
    if m % element == 0:
        ans += [m // element]
    else:
        ans += [m // element + 1]
writ = ans[0]
tr = 0
for element in ans:
    if element != writ:
        tr = -1
if tr == -1:
    print(tr)
else:
    print(writ)

n, m = list(map(int, input().split()))
kv = [None] * 101
boo = [False] * 101
for i in range(m):
    k, j = list(map(int, input().split()))
    kv[k] = j
for j in range(1, 101):
    qw = True
    for i in range(len(kv)):
        if kv[i] is not None:
            a = (i - 1) // j + 1
            if kv[i] != a:
                qw = False
    boo[j] = qw
a = sum(boo)
first = 0
q = set()
for i in range(len(boo)):
    if boo[i]:
        q.add((n - 1) // i + 1)
        


if len(q) == 1:
    print(q.pop())
else:
    print(-1)
            
        
        
        


n, m = list(map(int, input().split()))
data = []
fl = [0] * 1000000
an = -1
f = 0
for i in range(m):
    data += [list(map(int, input().split()))]
    fl[data[i][0]] = data[i][1]
    if data[i][0] == n:
        an = data[i][1]
    f = max(data[i][1], f)


if an != -1:
    print(an)
    return
data.sort()

an = []
t = True
for i in range(m):
    if data[i][0] != data[i][1]:
        t = False
if t:
    an += [n]
    
for k in range(2, 10001):
    #print(k)
    t = True
    for i in range(m):
        f = data[i][0] // k + min(1, data[i][0] % k)
        if data[i][1] != f:
            t = False
            break
    if not t:
        continue
    
    an += [n // k + min(1, n % k)]
    #print(an)

if len(set(an)) == 1:
    print(an[0])
else:
    print(-1)


n, m = list(map(int, input().split()))
v = []
for i in range(m):
    v.append(list(map(int, input().split())))
ans = []
for i in range(1, 101):
    o = True
    for p in v:
        if (p[0] - 1) // i != p[1] - 1:
            o = False
            break
    if o:
        if not(((n - 1) // i + 1) in ans):
            ans.append(((n - 1) // i + 1))
if len(ans) == 1:
    print(ans[0])
else:
    print(-1)


def first(n, m, line):
    for i in range(0, n): 
        k, f = list(map(int, input().split())) 
        res = [] 
        for j in range(1, 101): 
            if j * f >= k and j * (f - 1) < k: 
                res.append(j) 
        line.append(res) 
        res = [] 
    return line


def check(n, m, hz):
    for i in range(1, 101): 
        dno = 0 
        for elem in line: 
            if i in elem: 
                dno += 1 
        if dno == n: 
            hz.append(i)
    return hz


m, n = list(map(int, input().split())) 
line = [] 
line = first(n, m, line)
hz = [] 
hz = check(n, m, hz)
ans = [] 

for element in hz: 
    if m % element == 0: 
        ans.append(m // element)
    else: 
        ans.append(m // element + 1)
smth = ans[0] 
answ = 0 
for element in ans: 
    if element != smth: 
        answ = -1 
if answ == -1: 
    print(answ) 
else: 
    print(smth)


m, n = map(int, input().split())
arr = []
for i in range(n):
    a, b = map(int, input().split())
    arr.append((a, b))
ans = set()
for k in range(1, 150):
    fl = True
    for i in range(n):
        if ((arr[i][0] - 1) // k + 1) != arr[i][1]:
            fl = False
            break
    if fl: ans.add((m - 1) // k + 1)
if len(ans) == 1:
    for i in ans:
        print(i)
else:
    print(-1)

k = []
n, m = list(map(int, input().split(" ")))
for i in range(m):
	x, y = list(map(int, input().split(' ')))
	k.append([x, y])

def ok(x):
	for i in k:
		if (i[0]-1)//x+1!=i[1]:
			return False
	return True

poss = []
for x in range(1, 101):
	if ok(x):
		poss.append((n-1)//x+1)

if len(list(set(poss))) == 1:
	print(poss[0])
else:
	print(-1)




import sys, os
n, m = map(int, input().split())
mi = []
ma = []
if m == 0:
    if n == 1:
        print(1)
    else:
        print(-1)
    return
    return
    os.abort()
for i in range(m):
    a, b = map(int, input().split())
    if b == 1:
        ma.append(1000000000)
        mi.append(a)
        if n <= a:
            print(1)
            return
            return
            os.abort()
    else:
        mak = (a - 1) // (b - 1)
        ma.append(mak)
        if a % b == 0:
            mi.append(a // b)
        else:
            mi.append((a // b ) + 1)
#print(mi, ma)
mik = min(ma)
mak = max(mi)
if n % mik == 0:
    a = n // mik
else:
    a = (n // mik) + 1

if n % mak == 0:
    b = n // mak
else:
    b = (n // mak) + 1
if a == b:
    print(b)
else:
    print(-1)

n, m = map(int, input().split())
l = set()
s = {i for i in range(1, 101)}
b = False
for i in range(m):
  k, f = map(int, input().split())
  if k == n:
    print(f)
    b = True
    break
  j = 1
  if f == 1:
    l = {i for i in range(k, 101)}
  else:
    while j <= (k-j)//(f-1):
      if (k-j)%(f-1) == 0:
        l.add((k-j)//(f-1))
        j += f-1
      else:
        j += 1
  s &= l
  l.clear()
a = -1
if b == False:
  t = True
  for j in s:
    if a == -1:
      a = (n-1)//j
    else:
      if (n-1)//j != a:
        print(-1)
        t = False
        break
  if t == True:
    print(a+1)

n, m = map(int, input().split())
min_ = 10000
max_ = 0
for i in range(m):
    k, f = map(int, input().split())
    if f > 1:
        min_ = min(k / (f - 1), min_)
    max_ = max(k / f, max_)
min_, max_ = max_, min_


if(min_ != int(min_)):
    min_ +=1
min_ = int(min_)

if (max_ != int(max_)):
    max_+=1
max_ = int(max_)

#print(min_, max_)

s = set()
for i in range(max(1, min_), max_):
    b = n // i
    if (n % i) != 0:
        b+=1
    s.add(b)
if len(s) == 1:
    print(b)
else:
    print(-1)

n,m=list(map(int,input().split()))
k=[0]*m
f=[0]*m
l=1
r=100
for i in range(m):
    k[i],f[i]=list(map(int,input().split()))
for i in range(m):
    fl=True
    for kol in range(l,r+1):
        ch=k[i]-(f[i]-1)*kol
        if ch>0 and ch<=kol:
            if fl:
                l=kol
                fl=False
        elif not fl:
            r=kol-1
            break
    if r-l==0:
        print((n+r-1)//r)
        break
else:
    kok=(n+r-1)//r
    for kol in range(l,r):
        if kok!=(n+kol-1)//kol:
            print(-1)
            break
    else:
        print(kok)
                


n, m = map(int, input().split())

l = -100
r = 100
for i in range(m):
    k, f = map(int, input().split())
    l = max(l, (k + f - 1) // f)
    if(f != 1):
        r = min(r, (k - 1) // (f - 1))

if(l == r):
    print((n + r - 1) // r)
elif ((n + r - 1) // r == (n + l - 1) // l):
    print((n + r - 1) // r)
else:
    print(-1)

n, m = map(int, input().split())
list1 = []
ans = set()
if n == 1:
    print(1)
else:
    for i in range(m):
        list1.append(list(map(int, input().split())))
    for i in range(1, 101):
        if len(ans) > 1:
            print(-1)
            break
        for j in range(len(list1)):
            if (list1[j][0] - 1) // i + 1 != list1[j][1]:
                break
        else:
            ans.add((n - 1) // i + 1)
    else:
        if len(ans) == 1:
            print(*list(ans))
        else:
            print(-1)

import math

def f(m):
    nonlocal h
    f = True
    for i in range(len(h)):
        for j in h[i]:
            if not(j <= i * m and j > (i - 1) * m ):
                f = False
    return f

n, m = map(int, input().split())
h  = [[] for i in range(110)]
for i in range(m):
    a, b = map(int, input().split())
    h[b].append(a)
k = 0
ans = []
for i in range(1, 110):
    if f(i):
        k += 1
        ans.append(i)
fl = False
for i in range(len(h)):
    for j in h[i]:
        if j == n:
            fl = True
            ans1 = i
if fl:
    print(ans1)
elif m == 0 and n == 1:
    print(1)
elif k > 1:
    pr = math.ceil(n / ans[0])
    fl1 = True
    for i in range(1, len(ans)):
        if pr != math.ceil(n / ans[i]):
            fl1 = False
    if not fl1:
        print(-1)
    else:
        print(pr)
elif k < 1:
    print(-1)
else:
    print(math.ceil(n / ans[0]))


n,m=list(map(int,input().split()))
k=[]
f=[]
for i in range(m):
    u,p=list(map(int,input().split()))
    k.append(u)
    f.append(p)
def ok(x):
    for i in range(m):
        if (k[i]-1)//x+1!=f[i]:
            return False
    return True
a=[]
for i in range(1,101):
    if(ok(i)):
        a.append((n-1)//i+1)
if len(list(set(a)))==1:
    print(a[0])
else:
    print(-1)


n, m = list(map(int, input().split()))

n = n - 1
et = []
for i in range(m):
    et.append(tuple(map(lambda x: int(x) - 1, input().split())))
et.sort()
res = -1
if n == 0:
    res = 1
elif len(et) == 0:
    pass
else:
    et = [(-1, 0)] + et
    for i in range(len(et) - 1):
        if et[i][0] <= n <= et[i+1][0] and et[i][1] == et[i+1][1]:
            res = et[i][1] + 1
            break
    et = et[1:]
    if res == -1 and et[-1][1] != 0:
        y = []
        
        for i in range(1, et[-1][0] // et[-1][1] + 1):
            fl = True
            for j in range(len(et)):
                if et[j][0] // i != et[j][1]:
                    fl = False
                    break
            if fl:
                y.append(i)
        y1 = set([(n // tmp + 1) for tmp in y])
        if len(y1) == 1:
            res = y1.pop()
print(res)