n = int(input())
m = int(input())
bc = [list(map(int,input().split())) for i in range(m)] 

p = [i for i in range(n+1)]
bc.sort(key = lambda x:-x[0])
for b,c in bc:
  c%=b
  new = []
  for i in p:
    if i % b == c:
      new.append(i)
  p = new
if not p:
  print("NaN")
else:
  print(p[0])