import sys
import math

def main():
    N = int(sys.stdin.readline())
    M = int(sys.stdin.readline())
    congruences = []
    for _ in range(M):
        B, C = map(int, sys.stdin.readline().split())
        C_mod = C % B
        congruences.append((B, C_mod))
    
    current_a = 0
    current_mod = 1
    for B, C in congruences:
        d = math.gcd(current_mod, B)
        if (current_a - C) % d != 0:
            print("NaN")
            return
        m1 = current_mod // d
        b1 = B // d
        c1 = (C - current_a) // d
        inv = pow(m1, -1, b1)
        k0 = (c1 * inv) % b1
        x0 = current_a + k0 * current_mod
        new_mod = current_mod * B // d
        new_a = x0 % new_mod
        current_a, current_mod = new_a, new_mod
    
    if current_a <= N:
        print(current_a)
    else:
        print("NaN")

if __name__ == "__main__":
    main()