import sys input = sys.stdin.buffer.readline def solve(N, M, V): MAX = 10 ** 5 mod_table = [None] * (MAX + 1) for c, b in V: if mod_table[b] is None: mod_table[b] = c elif mod_table[b] != c: return "NaN" res_table = [0] * (N + 1) for i, mod in enumerate(mod_table): if mod is None: continue for x in range(mod, N + 1, i): res_table[x] += 1 for i in range(N + 1): if res_table[i] == M: return i return "NaN" 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, M, V))