#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int N,M;
int val[1<<17];
bool isp[1<<17];
main()
{
	cin>>N>>M;
	for(int i=1;i<=1e5;i++)val[i]=-1;
	for(int i=0;i<M;i++)
	{
		int B,C;cin>>B>>C;
		C=(C%B+B)%B;
		if(val[B]==-1)val[B]=C;
		else if(val[B]!=C)
		{
			cout<<"NaN"<<endl;
			return 0;
		}
	}
	vector<pair<int,int> >Q;
	int mv=0;
	for(int p=2;p<=1e5;p++)if(!isp[p])
	{
		for(int i=p+p;i<=1e5;i+=p)isp[i]=true;
		vector<pair<int,int> >x;
		for(int i=p;i<=1e5;i+=p)if(val[i]!=-1)
		{
			int u=i,t=1;
			while(u%p==0)
			{
				u/=p;
				t*=p;
			}
			x.push_back(make_pair(t,val[i]%t));
		}
		if(!x.empty())
		{
			sort(x.begin(),x.end());
			int C=x.back().second,B=x.back().first;
			for(pair<int,int>p:x)
			{
				if(C%p.first!=p.second)
				{
					cout<<"NaN"<<endl;
					return 0;
				}
			}
			Q.push_back(make_pair(C,B));
			mv=max(mv,C);
		}
	}
	for(int n=mv;n<=N;n++)
	{
		bool ok=true;
		for(pair<int,int>p:Q)
		{
			if(n%p.second!=p.first)
			{
				ok=false;
				break;
			}
		}
		if(ok)
		{
			cout<<n<<endl;
			return 0;
		}
	}
	cout<<"NaN"<<endl;
}