记录编号	30596	评测结果	AAAAAAAAAA
题目名称	[NOIP 2006]开心的金明	最终得分	100
用户昵称	Oo湼鞶oO	是否通过	通过
代码语言	Pascal	运行时间	0.083 s
提交时间	2011-10-30 17:19:52	内存使用	3.09 MiB

program happy;
var
  a,b,n,m,i,j:longint;
  f:array[0..25,0..30000]of longint;
  jz,tj:array[1..25]of longint;
begin
  assign (input,'happy.in');
  reset (input);
  assign (output,'happy.out');
  rewrite (output);
    readln (n,m);
    for i:=1 to m do
    begin
      readln (a,b);
      tj[i]:=a;
      jz[i]:=a*b
    end;
    for i:=1 to m do
      for j:=1 to n do
      begin
        f[i,j]:=f[i-1,j];
        if j-tj[i]>=0 then
          if f[i-1,j-tj[i]]+jz[i]>=f[i,j] then
            f[i,j]:=f[i-1,j-tj[i]]+jz[i]
      end;
    writeln (f[m,n]);
  close (input);
  close (output)
end.