记录编号	137854	评测结果	AAAAAAAAAA
题目名称	韩信点兵	最终得分	100
用户昵称	WW TT	是否通过	通过
代码语言	Pascal	运行时间	0.002 s
提交时间	2014-11-05 12:12:39	内存使用	0.17 MiB

var ans,t,bb,m,n:int64;
    i,j:longint;
	f:array[1..10,1..2] of int64;
procedure dfs(x,y,z:int64);
var i,j,te,tt,hx,bb:int64;
begin
if x=m then begin ans:=y;exit;end;
i:=1;
hx:=y mod f[x+1,1];
while i<=f[x+1,1] do
begin
te:=y mod f[x+1,1];
if (te=hx)and(i<>1) then begin writeln(-1);close(output);halt;end;
if te=f[x+1,2] then
begin
dfs(x+1,y,z*f[x+1,1]);
exit;
end;
y:=y+z;
i:=i+1;
end;
writeln(-1);close(output);halt;
end;


procedure init;
var b:int64;
begin
readln(n,m);
t:=1;
for i:=1 to m do
begin
readln(f[i,1],f[i,2]);
t:=t*f[i,1];
end;
for i:=1 to m-1 do
 for j:=i+1 to m do
  if f[i,1]<f[j,1]
  then begin b:=f[i,1];f[i,1]:=f[j,1];f[j,1]:=b;
  b:=f[i,2];f[i,2]:=f[j,2];f[j,2]:=b;
  end;
bb:=f[1,1]+f[1,2];
dfs(1,bb,f[1,1]);
end;

begin
assign(input,'HanXin.in');
assign(output,'HanXin.out');
reset(input);
rewrite(output);
init;
if ans>n then begin writeln(-1);close(output);halt;end;
ans:=ans+((n-ans) div t)*t;
writeln(n-ans);
close(output);
end.