记录编号	147877	评测结果	AAAAAAAAAA
题目名称	韩信点兵	最终得分	100
用户昵称	sqyon	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2015-02-04 21:31:42	内存使用	0.29 MiB

#include <cstdio>
#include <queue>
 
#define maxn 15
#define LL long long
 
using namespace std;
 
LL n, N, M, m[maxn], a[maxn], ans;
bool flag;
 
void gcd(LL a, LL b, LL &x, LL &y)
{
	if (!b)
	{
		x = 1;
		y = 0;
		return ;
	}
	gcd(b, a % b, y, x);
	y -= x * (a / b);
	return ;
}
 
inline void init()
{
	M = 1;
	scanf("%lld %lld", &N, &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%lld %lld", m + i, a + i);
		M *= m[i];
		if (m[i])
			flag = true;
	}
	return ;
}
 
inline void CRT()
{
	LL w, x, y;
	for (int i = 0; i < n; i++)
	{
		w = M / m[i];
		gcd(w, m[i], x, y);
		ans = (ans + a[i] * w * x) % M;
	}
	return ;
}
 
int main()
{
	freopen("HanXin.in", "r", stdin);
	freopen("HanXin.out", "w", stdout);
	
	init();
	if (!flag)
	{
		printf("-1");
		return 0;
	}
	CRT();
	while (ans + M <= N)
		ans += M;
	if (ans > N)
	{
		printf("-1");
		return 0;
	}
	printf("%lld", N - ans);
	return 0;
}