program lazy;
var m:array[0..10001] of integer;
  p,t,a,b:array[0..10001] of integer;
  n,k,i,j,l:integer;
procedure sort(x:integer);
var tmp,y:integer;
begin
  while (x*2<=l) and (a[x]>a[x*2])
    or ((x*2+1<=l)and(a[x]>a[x*2+1])) do
  begin
    if x*2=l then
      y:=x*2
    else if a[x*2]<a[x*2+1]
          then y:=x*2
          else y:=x*2+1;
    tmp:=a[y]; a[y]:=a[x]; a[x]:=tmp;
    tmp:=b[y]; b[y]:=b[x]; b[x]:=tmp;
    x:=y;
  end;
end;
procedure delete;
begin
  a[1]:=a[l]; b[1]:=b[l];
  dec(l);
  sort(1);
end;
begin
  assign(input,'lazy.in'); reset(input);
  assign(output,'lazy.out'); rewrite(output);
  readln(n,k);
  for i:=1 to k do
  begin
    readln(p[i],t[i]);
    a[i]:=p[i]; b[i]:=t[i];
  end;
  l:=k;
  for i:=(k div 2) downto 1 do sort(i);
  for i:=1 to k do
  begin
    p[i]:=a[1]; t[i]:=b[1];
    delete;
  end;
  m[n+1]:=0;
  j:=k;
  for i:=n downto 1 do
  begin
    if p[j]<>i then m[i]:=m[i+1]+1
    else
      while p[j]=i do
      begin
        if m[i+t[j]]>m[i] then m[i]:=m[i+t[j]];
        dec(j);
      end;
  end;
  writeln(m[1]);
  close(input); close(output);
end.