noip2006/happy.pas

   1 program happy;
   2
   3 var
   4 n,m,p,i,j:longint;
   5 v,w:array [1..25] of longint;
   6 f:array [0..30000] of longint;
   7
   8 function max(x,y:longint):longint;
   9 begin
  10   if x>y then max:=x else max:=y;
  11 end;
  12
  13 begin
  14   readln(n,m);
  15   for i:=1 to m do
  16     begin
  17       readln(v[i],p);
  18       w[i]:=v[i]*p;
  19     end;
  20   for i:=1 to m do
  21     for j:=n downto v[i] do
  22       f[j]:=max(f[j],f[j-v[i]]+w[i]);
  23   writeln(f[n]);
  24 end.
  25