记录编号	726	评测结果	AAAAAAAAAA
题目名称	[NOIP 2005]采药	最终得分	100
用户昵称	rottenwood	是否通过	通过
代码语言	Pascal	运行时间	10.000 s
提交时间	2008-07-21 16:19:00	内存使用	0.00 MiB

program medic;
type
shuzu=array[0..10000] of longint;
shuzu1=array[0..2000,0..2000]of longint;
var
i,j,n,a:longint;
t,m:longint;
b:shuzu1;
f1,f2:text;
s,s1:shuzu;
function max(x,y:longint):longint;
begin
if x>y then max:=x
else max:=y;
end;
begin
assign(f1,'medic.in');reset(f1);
assign(f2,'medic.out');rewrite(f2);
readln(f1,t,m);
fillchar(b,sizeof(b),0);
for i:=1 to m do
  readln(f1,s[i],s1[i]);
for i:=1 to m do
   for j:=1 to t do
    if j-s[i]<0 then
     b[i,j]:=b[i-1,j]
    else b[i,j]:=max(b[i-1,j],b[i-1,j-s[i]]+s1[i]);
       writeln(f2,b[m,t]);
      close(f2);
      end.