import sys
import math

def main():
    N = int(sys.stdin.readline())
    M = int(sys.stdin.readline())
    B = []
    C_mod = []
    for _ in range(M):
        b, c = map(int, sys.stdin.readline().split())
        B.append(b)
        C_mod.append(c % b)  # Compute C_m mod B_m here

    if M == 0:
        print(0 if 0 <= N else "NaN")
        return

    # Initialize with the first congruence
    a = C_mod[0]
    current_modulus = B[0]

    for i in range(1, M):
        c_i = C_mod[i]
        b_i = B[i]

        d = math.gcd(current_modulus, b_i)
        if (a - c_i) % d != 0:
            print("NaN")
            return

        # Compute the new modulus and new_a
        m_div = current_modulus // d
        b_div = b_i // d

        # Calculate modular inverse
        inv = pow(m_div, -1, b_div)

        k = ((c_i - a) // d) * inv
        k %= b_div  # Ensure k is non-negative and within the modulus

        x = a + k * current_modulus
        new_modulus = current_modulus * b_i // d
        a = x % new_modulus
        current_modulus = new_modulus

    if a <= N:
        print(a)
    else:
        print("NaN")

if __name__ == "__main__":
    main()