记录编号	21217	评测结果	AAAAAAAAAA
题目名称	懒人的工作	最终得分	100
用户昵称	donny	是否通过	通过
代码语言	Pascal	运行时间	0.046 s
提交时间	2010-11-08 19:15:33	内存使用	0.26 MiB

program nike;
var
  i,j,l:longint;
  n,k:longint;
  a:array[0..10000,1..3]of longint;
  f:array[1..10001]of longint;
function max(x,y:longint):longint;
begin
  if x>y then exit(x)
  else exit(y);
end;
procedure sort(x,y:longint);
var
  i,j,k,l:longint;
begin
  i:=x;
  j:=y;
  k:=a[(x+y)div 2,1];
  repeat
    while a[i,1]<k do inc(i);
    while a[j,1]>k do dec(j);
    if i<=j then
    begin
      l:=a[i,1];
      a[i,1]:=a[j,1];
      a[j,1]:=l;
      l:=a[i,2];
      a[i,2]:=a[j,2];
      a[j,2]:=l;
      inc(i);
      dec(j);
    end;
  until i>j;
  if i<y then sort(i,y);
  if x<j then sort(x,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(a[i,1],a[i,2]);
  sort(1,k);
  f[n+1]:=0;
  i:=n;
  a[0,1]:=0;
  while i<>0 do
  begin
    if a[k,1]=i then
    begin
      while a[k,1]=i do
      begin
        f[i]:=max(f[i],f[i+a[k,2]]);
        dec(k);
      end;
    end
    else
    begin
      f[i]:=f[i+1]+1;
    end;
    dec(i);
  end;
  writeln(f[1]);
  close(input);
  close(output);
end.