记录编号	138028	评测结果	AAAAAAAAAA
题目名称	韩信点兵	最终得分	100
用户昵称	ok	是否通过	通过
代码语言	C++	运行时间	0.006 s
提交时间	2014-11-05 16:18:49	内存使用	0.32 MiB

#include <fstream>
using namespace std;
ifstream input("HanXin.in");
ofstream output("HanXin.out");
long long m,n,s=1,chu[12],yu[12],z=0;
long long ni(long long xx,long long yy,long long zz)
{
	if(xx%zz==1) return xx;
	return ni(xx+yy,yy,zz);
}
int main()
{
	long long i;
	input>>m>>n;
	for(i=1;i<=n;i++)
	{
		input>>chu[i]>>yu[i];
		s*=chu[i];
	}
	for(i=1;i<=n;i++)
	{
		z=(z+yu[i]*ni(s/chu[i],s/chu[i],chu[i]))%s;
	}
	if(z>=m)
	{
		if(z>m) output<<"-1"<<endl;
		else output<<m<<endl;
	}
	else
	{
		long long res=0;
		res=m-s*(m/s)+s-z;
		output<<res%s<<endl;
	}
	input.close();
	output.close();
	return 0;
}