记录编号	5287	评测结果	AAAAAAAAAA
题目名称	[NOIP 2006]开心的金明	最终得分	100
用户昵称	ReimBurSe.	是否通过	通过
代码语言	Pascal	运行时间	0.109 s
提交时间	2008-10-25 23:39:59	内存使用	3.09 MiB

Program happy;

Type
sc=array [0..25,0..30000] of longint;
sc1=array [1..25] of integer;

Var
i,j,temp:longint;
s:sc;
n,m:integer;
v,p:sc1;

Begin
assign(input,'happy.in');
assign(output,'happy.out');
reset(input);
rewrite(output);
readln(n,m);
for i:=1 to m do
 readln(v[i],p[i]);
for i:=0 to m do
 for j:=0 to n do
  s[i,j]:=0;
for i:=1 to m do begin
 for j:=1 to n do begin
  s[i,j]:=s[i-1,j];
  if j>=v[i] then begin
   temp:=v[i]*p[i]+s[i-1,j-v[i]];
   if temp>s[i,j] then s[i,j]:=temp;
  end;
 end;
end;
write(s[m,n]);
close(input);
close(output);
End.