记录编号	138553	评测结果	AAAAAAAAAA
题目名称	韩信点兵	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2014-11-06 00:18:33	内存使用	0.32 MiB

#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cstring>
#include <queue>
#include <cmath>
#include <iostream>
typedef long long LL;
using namespace std;
inline int lowbit(int x){return x & -x;}
int gcd(int a, int b){return (!a) ? b : gcd(b % a, b);}
template<typename T>T exgcd(T a, T b, T &x, T &y){
	if(!a){x = 0, y = 1; return b;}
	T d = exgcd(b % a, a, y, x);
	x -= (b/a) * y;
	return d;
}
template<typename T>inline void getint(T &x){
	char c = getchar();
	while(!isdigit(c))c = getchar();
	x = c - '0';
	while(isdigit(c = getchar()))x = x * 10 - '0' + c;
}
/*=====================================*/
inline LL inv(LL a, LL mod){
	LL x, y;
	if(exgcd(a, mod, x, y) != 1)return -1;
	return (x % mod + mod) % mod;
}
LL n, M = 1, N[11], e, S = 0;
int P[11], a[11], m;

inline void init(){
	getint(n), getint(m);
	for(int i = 0;i < m;++i){
		getint(P[i]), getint(a[i]);
		M *= P[i];
	}
	for(int i = 0;i < m;++i){
		N[i] = M / P[i];
		e = N[i] * inv(N[i], P[i]) % M;
		S = (S + e * a[i]) % M;
	}
}

inline void work(){
	LL x, y;
	x = S % M;
	if(x > n){printf("-1\n");return;}
	printf("%lld\n", (n-x) % M);
}

int main(){
	#if defined DEBUG
	freopen("test", "r", stdin);
	#else
	freopen("HanXin.in", "r", stdin);
	freopen("HanXin.out", "w", stdout);
	#endif
	
	init();
	
	work();
	
	return 0;
}