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

uses math;
type thing=record
      v,p,son:longint;
      s:array[1..10]of longint;
     end;
const fg:array[1..12]of longint=(1,2,4,8,16,32,64,128,256,512,1024,2048);
var n,m,i,j,k,l,g,bw,bww,wb,pt,wbb,bwwb:longint; a:array[1..60]of thing; b:array[1..60]of longint;
    f:array[0..1,1..3200]of longint;
function get(x:longint):longint;
begin
 case x of
  1: exit(1);
  2: exit(2);
  4: exit(3);
  8: exit(4);
  16: exit(5);
  32: exit(6);
  64: exit(7);
  128: exit(8);
  256: exit(9);
  512: exit(10);
  1024: exit(11);
 end;
end;
begin
assign(input,'budgetb.in'); assign(output,'budgetb.out'); reset(input); rewrite(output);
 readln(n,m,g); for i:=1 to m do a[i].son:=0; n:=n div 10;
 for i:=1 to m do
  begin
   readln(a[i].v,a[i].p,j); a[i].v:=a[i].v div 10;
   if j=0 then begin inc(pt); b[pt]:=i; end
   else begin inc(a[j].son); a[j].s[a[j].son]:=i; end;
  end;
 for i:=1 to pt do
  begin
   wbb:=b[i]; f[i and 1]:=f[(i+1)and 1];
   for j:=0 to fg[a[wbb].son+1]-1 do
    begin
     k:=a[wbb].v; l:=a[wbb].v*a[wbb].p;
     bw:=j;
     while bw<>0 do
      begin
       bww:=bw and -bw;
       bwwb:=get(bww);
       k:=k+a[a[wbb].s[bwwb]].v;
       l:=l+a[a[wbb].s[bwwb]].v*a[a[wbb].s[bwwb]].p;
       bw:=bw-bww;
      end;
for wb:=n downto k do begin
 if f[i and 1,wb]<f[(i+1)and 1,wb-k]+l then
  f[i and 1,wb]:=f[(i+1)and 1,wb-k]+l;
if f[(i+1)and 1,wb]>f[i and 1,wb] then f[i and 1,wb]:=f[(i+1)and 1,wb]; end;
    end;
  end;
 write(max(f[pt and 1,n],f[(pt+1)and 1,n])*10);
close(input); close(output);
end.