program lazy(input,output);

var
  i,j,n,k:longint;
  p,t,f:array[1..10001]of longint;

procedure qsort(l,h:longint);
  var
    i,j,m,tmp:longint;
  begin
    i:=l;
    j:=h;
    m:=p[(i+j) div 2];

   repeat
     while p[i]<m do
       inc(i);

     while m<p[j] do
       dec(j);

     if i<=j then
     begin
       tmp:=p[i];
       p[i]:=p[j];
       p[j]:=tmp;

       tmp:=t[i];
       t[i]:=t[j];
       t[j]:=tmp;

       inc(i);
       dec(j);
     end;
   until i>j;

   if i<h then
     qsort(i,h);

   if j>l then
     qsort(l,j);
  end;

begin
  assign(input,'lazy.in');
  reset(input);
  assign(output,'lazy.out');
  rewrite(output);

  readln(n,k);

  for i:=1 to k do
    readln(p[i],t[i]);

  qsort(1,k);

  j:=k;
  for i:=n downto 1 do
    if i=p[j] then
      while i=p[j] do
      begin
        if f[i+t[j]]>f[i] then 
          f[i]:=f[i+t[j]];

        dec(j);
      end
    else
      f[i]:=f[i+1]+1;

  writeln(f[1]);

  close(input);
  close(output);
end.