import sys
import math

def main():
    N = int(sys.stdin.readline())
    M = int(sys.stdin.readline())
    pairs = []
    for _ in range(M):
        B, C = map(int, sys.stdin.readline().split())
        pairs.append((B, C))
    
    a = 0
    mod = 1  # current modulus
    
    for B, C in pairs:
        # Adjust C to be non-negative modulo B
        C %= B
        
        d = math.gcd(mod, B)
        if (a - C) % d != 0:
            print("NaN")
            return
        
        # Compute k0, m1, b1
        k0 = (C - a) // d
        m1 = mod // d
        b1 = B // d
        
        # Handle the case where m1 and b1 are both 1
        if m1 == 1 and b1 == 1:
            k = 0
        else:
            # Compute modular inverse of m1 modulo b1
            inv = pow(m1, -1, b1)
            k = (k0 * inv) % b1
        
        x = a + k * mod
        new_mod = mod * B // d
        new_a = x % new_mod
        
        a = new_a
        mod = new_mod
    
    if a <= N:
        print(a)
    else:
        print("NaN")

if __name__ == '__main__':
    main()