#include #include using namespace std; using namespace atcoder; void fast_io() { ios_base::sync_with_stdio(false); cin.tie(nullptr); } int main() { fast_io(); int n, m; cin >> n >> m; vector b(m), c(m); for (int i = 0; i < m; i++) { cin >> b[i] >> c[i]; c[i] = (c[i] % b[i] + b[i]) % b[i]; } auto [y, z] = crt(c, b); if (z == 0 || y > n) { cout << "NaN" << endl; } else { cout << y << endl; } }