记录编号	11775	评测结果	AAAAAAAAAA
题目名称	[NOIP 2006]开心的金明	最终得分	100
用户昵称	maxiem	是否通过	通过
代码语言	Pascal	运行时间	0.547 s
提交时间	2009-08-21 16:45:07	内存使用	2.97 MiB

program happy;
var
  price,item:array [1..25] of longint;
  dp:array [0..30000,1..25] of longint;
  i,n,m,v,p:integer;
procedure get(money,node:integer);
begin
  if node=m then begin
    if money>=price[m] then dp[money,m]:=item[m] else dp[money,m]:=0;
  end
  else begin
    if money>=price[node] then get(money-price[node],node+1);
    get(money,node+1);
    if money>=price[node] then begin
      if dp[money-price[node],node+1]+item[node]>dp[money,node+1]
        then dp[money, node]:=dp[money-price[node],node+1]+item[node]
        else dp[money,node]:=dp[money,node+1];
    end
    else dp[money,node]:=dp[money,node+1];
  end;
end;
begin
  fillchar (dp,sizeof(dp),0);
  assign (input,'happy.in');
  reset (input);
  readln (n,m);
  for i:=1 to m do begin
    readln (v,p);
    price[i]:=v;
    item[i]:=v*p;
  end;
  close (input);
  assign (output,'happy.out');
  rewrite (output);
  get(n,1);
  writeln (dp[n,1]);
  close (output);
end.