记录编号	17331	评测结果	AAAAAAAAAA
题目名称	[NOIP 2006]开心的金明	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	Pascal	运行时间	0.093 s
提交时间	2010-07-18 08:22:56	内存使用	3.09 MiB

program happy;

var aa:array[0..30000,0..25]of longint;
    v,p:array[1..30]of longint;
    n,m,i,j:longint;
    f:text;

function max(a,b:longint):longint;
 begin
  if a>b then
   max:=a else max:=b;
 end;

begin
 assign(f,'happy.in');
 reset(f);
 readln(f,m,n);

 for i:=1 to n do
  readln(f,v[i],p[i]);

 close(f);

 for i:=1 to m do
  for j:=1 to n do
   if v[j]>i then
    aa[i,j]:=aa[i,j-1] else
      aa[i,j]:=max(aa[i-v[j],j-1]+p[j]*v[j],aa[i,j-1]);

 assign(f,'happy.out');
 rewrite(f);
 writeln(f,aa[m,n]);
 close(f);
end.