记录编号	87424	评测结果	AAAAAAAAAA
题目名称	[NOIP 2006]开心的金明	最终得分	100
用户昵称	筽邝	是否通过	通过
代码语言	Pascal	运行时间	0.033 s
提交时间	2014-02-04 17:40:49	内存使用	3.14 MiB

program cojs71;
type
  node=record
    cost,value:longint;
  end;
var
  n,m,i,j:longint;
  a:array[1..25]of node;
  f:array[0..25,0..30000]of longint;

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

begin
assign(input,'happy.in');reset(input);
assign(output,'happy.out');rewrite(output);

  readln(n,m);
  for i:=1 to m do
    readln(a[i].cost,a[i].value);

  for i:=1 to m do
  for j:=0 to n do
  begin
    f[i,j]:=f[i-1,j];
	if j>=a[i].cost then f[i,j]:=max(f[i-1,j],f[i-1,j-a[i].cost]+a[i].cost*a[i].value);
  end;

  writeln(f[m,n]);

close(input);close(output);
end.