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

var n,maxn,d1,d2,d3,lcm,d4,d5,t:int64;
    m,i,j,k,o1,o2,o3:longint;
	a,b:array[1..20]of int64;
	bo:array[1..20]of boolean;
        c:boolean;

procedure init;
begin
readln(n,m);
lcm:=1;
for i:=1 to m do
begin
 read(a[i],b[i]);
 if a[i]>maxn then begin maxn:=a[i];o1:=i;end;
 lcm:=lcm*a[i];
end;
end;

procedure qsort(x,y:longint);
var i,j,m1,m2,o:longint;
begin
i:=x;j:=y;m1:=a[(x+y)>>1];
repeat
 while a[i]>m1 do inc(i);
 while a[j]<m1 do dec(j);
 if i<=j then
  begin
  o:=a[i];a[i]:=a[j];a[j]:=o;
  o:=b[i];b[i]:=b[j];b[j]:=o;
  inc(i);dec(j);
  end;
until i>j;
if i<y then qsort(i,y);
if x<j then qsort(x,j);
end;

procedure work;
begin
qsort(1,m);
d1:=b[1]-a[1];t:=a[1];
//for i:=1 to m do writeln(a[i],' ',b[i]);
while true do
begin
d1:=d1+t;//writeln(d1);readln;
  if (d1>n) then
  begin writeln(-1);exit;end;
c:=true;
for i:=2 to m do
if not bo[i] then
begin
 if d1 mod a[i]<>b[i] then
 begin c:=false;end;
 if d1 mod a[i]=b[i] then
 begin
  t:=t*a[i];bo[i]:=true;
 end;
end;
if c then break;
end;
//writeln(d2);
d3:=n-d1;
d4:=d3 mod lcm;
writeln(d4);
end;

begin
assign(input,'HanXin.in');reset(input);
assign(output,'HanXin.out');rewrite(output);
init;
work;
close(output);
end.