import sys
from math import gcd

def extended_gcd(a, b):
    if b == 0:
        return (a, 1, 0)
    else:
        g, x, y = extended_gcd(b, a % b)
        return (g, y, x - (a // b) * y)

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())
        congruences.append((B, C))
    
    current_mod = 1
    current_rem = 0
    has_solution = True
    
    for B, C in congruences:
        c = C % B
        d = gcd(current_mod, B)
        if (current_rem - c) % d != 0:
            has_solution = False
            break
        
        m1 = current_mod
        a = current_rem
        m2 = B
        b = c
        
        g, x, y = extended_gcd(m1 // d, m2 // d)
        k0 = ((b - a) // d) * x % (m2 // d)
        new_rem = a + k0 * m1
        new_mod = (m1 * m2) // d
        new_rem %= new_mod
        
        current_rem = new_rem
        current_mod = new_mod
    
    if not has_solution:
        print("NaN")
    else:
        print(current_rem if current_rem <= N else "NaN")

if __name__ == "__main__":
    main()