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

program tz;   
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.  
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.