var m,i,j,k,ans,tp:longint;
    p,a:array[0..11] of longint;
    n:int64;
procedure init;
begin
  fillchar(p,sizeof(p),0);
  fillchar(a,sizeof(a),0);
  ans:=0;
  readln(n,m);
  for i:=1 to m do
  begin
    readln(p[i],a[i]);
  end;
end;

procedure work;
begin
  for i:=n downto 1 do
  begin
    tp:=0;
    for j:=1 to m do
	begin
	  if ((i mod p[j])=a[j]) then inc(tp);
	end;
	if tp=m then
	begin
	  writeln(n-i);
	  halt;
	end;
  end;
  writeln(-1);
end;

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