记录编号	1843	评测结果	AAAAAAAAAA
题目名称	[NOIP 2005]采药	最终得分	100
用户昵称	bly1991	是否通过	通过
代码语言	Pascal	运行时间	96.000 s
提交时间	2008-09-08 21:53:57	内存使用	0.00 MiB

program bly(input,output);
var 
  t,m:integer;
  g:array[1..100]of integer; 
  h:array[1..100]of integer; 
  f:array[0..100,-101..1000]of longint;
  i,j:integer;
  f1,f2:text;
begin
  assign(f1,'medic.in');
  reset(f1);
  readln(f1,t,m);
  for i:=1 to m do begin
    readln(f1,g[i],h[i]);
  end;
  for i:=1 to m do begin
    f[i]:=f[i-1];
    for j:=1 to t do begin
      f[i,j]:=f[i-1,j];
      if j-g[i]>=0 then
      if f[i-1,j]<f[i-1,j-g[i]]+h[i] then begin
        f[i,j]:=f[i-1,j-g[i]]+h[i];
      end;
    end;
  end;
  assign(f2,'medic.out');
  rewrite(f2);
  writeln(f2,f[i,j]);
  close(f2);
  close(f1);
end.