import sys from functools import lru_cache input = sys.stdin.buffer.readline """中国剰余定理 https://tjkendev.github.io/procon-library/python/math/chinese-remainder.html から拝借し、一部改変しています""" @lru_cache def extgcd(a, b): if b: d, y, x = extgcd(b, a % b) y -= (a // b) * x return d, x, y return a, 1, 0 # V = [(X_i, Y_i), ...]: X_i (mod Y_i) def remainder(N, V): x = 0 d = 1 for X, Y in V: g, a, b = extgcd(d, Y) x, d = (Y * b * x + d * a * X) // g, d * (Y // g) x %= d if x > N: return None if x % Y != X: return None return x def solve(N, V): res = remainder(N, V) if res is None: return "NaN" return res N = int(input()) M = int(input()) V = [] for _ in range(M): b, c = map(int, input().split()) c %= b V.append((c, b)) print(solve(N, V))