ll@n,@m;
ll x[2]{},y[2]{1};
rep(m){
	rd(y[1],x[1]);
	ll z=chineseRemainder(2,x,y);
	if(z<0||z>n){
		wt("NaN");
		exit(0);
	}
	x[0]=z;
	if(y[0]<n){
		y[0]=lcm(y(2));
	}
}
wt(x[0]);