记录编号	49563	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	还是“金明的预算方案”	最终得分	100
用户昵称	CAX_CPG	是否通过	通过
代码语言	Pascal	运行时间	0.022 s
提交时间	2012-11-08 14:54:17	内存使用	0.67 MiB

uses math;

var f:array[0..1,0..3200]of longint;
    c:array[0..60,0..500,0..2]of longint;
    v,w:array[1..60]of longint;
    vf:array[1..60]of boolean;
    i,j,k,n,m,s,q:longint;
    b:array[1..60,0..10]of longint;

procedure did(step,ans1,ans2,x:longint);
var ii:longint;
begin
 if step=j then
  begin
   inc(c[i,0,0]);
   c[i,c[i,0,0],1]:=ans1+v[i];
   c[i,c[i,0,0],2]:=ans2+w[i];
   exit;
  end;
 for ii:=x+1 to b[i,0]do
  begin
   did(step+1,ans1+v[b[i,ii]],ans2+w[b[i,ii]],ii);
  end;
end;

begin
 assign(input,'budgetb.in');reset(input);
 assign(output,'budgetb.out');rewrite(output);
 readln(n,m,s);n:=n div 10;
 for i:=1 to m do
  begin
   readln(v[i],w[i],q);v[i]:=v[i]div 10;
   w[i]:=w[i]*v[i];
   if q<>0 then
    begin inc(b[q,0]);b[q,b[q,0]]:=i;vf[i]:=true;end;
  end;
 for i:=1 to m do
  for j:=0 to b[i,0]do if not(vf[i])then did(0,0,0,0);
 for j:=1 to m do
  for k:=0 to c[j,0,0]do
   for i:=n downto c[j,k,1] do
    f[j and 1,i]:=max(f[j and 1,i],f[(j-1)and 1,i-c[j,k,1]]+c[j,k,2]);
 writeln(f[m and 1,n]*10);
 close(output);
end.