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

#include <fstream>
#include <string>
#include <algorithm>
using namespace std;
ifstream in("HanXin.in");
ofstream out("HanXin.out");
long long n,m,sum=1,cost=1,s=0,dost=1;
class node
{
public:
	long long a;
	long long b;
}rest[11];
long long compare(node x,node y)
{
	if(x.a<=y.a)return true;
	return false;
}
int main()
{
	long long i,j;
	in>>n>>m;
	for(i=1;i<=m;i++)
	{
		in>>rest[i].a>>rest[i].b;
		if(rest[i].b==0)rest[i].b=rest[i].a;
	}
	sort(rest+1,rest+m+1,compare);
	for(i=1;i<=m;i++)sum*=rest[i].a;
	for(i=1;i<=m;i++)
	{
		cost=1;
		for(j=1;j<=m;j++)
		{
			cost*=rest[j].a;
		}
		cost/=rest[i].a;
		dost=cost;
		while(cost%rest[i].a!=1)cost+=dost;
		cost=cost*rest[i].b;
		s+=cost;
	}
	//out<<s<<' '<<sum<<endl;
	if(s>n)
	{
		if(s>=sum)
		{
			if(s-(s-n+sum-1)/sum*sum>=0)out<<n-(s-(s-n+sum-1)/sum*sum)<<endl;
			else out<<-1<<endl;
		}
		else out<<-1<<endl;
	}
	if(s==n)out<<0<<endl;
	if(s<n)out<<n-(s+(n-s)/sum*sum)<<endl;
	//mark(175,180);
	in.close();
	out.close();
	return 0;
}