记录编号	871	评测结果	AAAAAAAAAA
题目名称	[NOIP 2006]开心的金明	最终得分	100
用户昵称	rottenwood	是否通过	通过
代码语言	Pascal	运行时间	10.000 s
提交时间	2008-07-22 19:46:37	内存使用	0.00 MiB

program happy;
type
shuzu=array[0..10000] of longint;
shuzu1=array[0..30000]of longint;
var
v,w:shuzu;
b:shuzu1;
i,j,m,n:longint;
f1,f2:text;
function max(x,y:longint):longint;
begin
if x>y then max:=x
else max:=y;
end;
begin
assign(f1,'happy.in');reset(f1);
assign(f2,'happy.out');rewrite(f2);
readln(f1,n,m);
for i:=1 to m do
begin
 readln(f1,v[i],w[i]);
 w[i]:=v[i]*w[i];
end;
for i:=1 to m do
  for j:=n downto v[i] do
    begin
     b[j]:=max(b[j],b[j-v[i]]+w[i]);
   end;
writeln(f2,b[n]);
close(f1);close(f2);
end.