ll@n,@m;
ll x[2],y[2];
rd(y[0],x[0]);
x[0]%=y[0];
rep(m-1){
	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[1]<ll_inf/y[0]){
		y[0]=lcm(y(2));
	}
}
wt(x[0]);