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

program cch(input,output,f1,f2);
var
 f1,f2:text;
 v,w:array[1..25] of integer;
 a:array[0..30000] of longint;
 max,i,j,n,m:longint;

begin
 assign(f1,'happy.in');
 assign(f2,'happy.out');
 reset(f1);
 rewrite(f2);
 readln(f1,n,m);
 for i:=1 to m do readln(f1,v[i],w[i]);
 for i:=0 to n do a[i]:=0;
 for i:=1 to m do
  for j:=n downto v[i] do
   if (a[j]<a[j-v[i]]+w[i]*v[i]) then
    a[j]:=a[j-v[i]]+w[i]*v[i];
 max:=0;
 for i:=1 to n do
  if a[i]>max then max:=a[i];
 writeln(f2,max);
 close(f1);
 close(f2);
end.