记录编号	137861	评测结果	WWWAAEEEEE
题目名称	韩信点兵	最终得分	20
用户昵称	冷颜少年	是否通过	未通过
代码语言	C++	运行时间	2.568 s
提交时间	2014-11-05 12:22:36	内存使用	0.31 MiB

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
int main()
{
	freopen("HanXin.in","r",stdin);
	freopen("HanXin.out","w",stdout);
	long long n,a[11],b[11],p;
	int m,i,j;
	vector<long long> s,t;
	cin>>n>>m;
	for(i=1;i<=m;i++)
	  cin>>a[i]>>b[i];
	for(i=1;i<=m-1;i++)
	  for(j=1;j<=m-i;j++)
		if(a[j]<a[j+1])
		{
			p=a[j];a[j]=a[j+1];a[j+1]=p;
			p=b[j];b[j]=b[j+1];b[j+1]=p;
		}
	p=a[1]+b[1];
	s.push_back(p);
	while(p<n)
	{
		p+=a[i];
		s.push_back(p);
	}
	if(p>n) s.pop_back();
	for(i=2;i<=m;i++)
	{
		for(j=0;j<s.size();j++)
		  if(s[j]%a[i]==b[i])
			t.push_back(s[j]);
		s=t;
		if(s.empty()) break;
		t.clear();
	}
	if(s.empty()) cout<<-1;
	else cout<<n-s[s.size()-1];
	return 0;
}