记录编号	49595	评测结果	AAAAAAAAAAAWAAWWWWAA
题目名称	还是“金明的预算方案”	最终得分	75
用户昵称	张来风飘	是否通过	未通过
代码语言	Pascal	运行时间	0.150 s
提交时间	2012-11-08 15:57:38	内存使用	8.22 MiB

program project1;
var son1,son2,v,w,q:array[0..65] of longint;
    f:array[0..65,0..32005] of longint;
    n,m,s,i:longint;
procedure init;
var i:longint;
begin
     assign(input,'budgetb.in');reset(input);
     assign(output,'budgetb.out');rewrite(output);
     read(n,m,s);
     for i:=1 to m do
     begin
          read(v[i],w[i],q[i]);
          if q[i]<>0 then
          begin
               if son1[q[i]]=0 then son1[q[i]]:=i else
               son2[q[i]]:=i;
          end;
     end;
end;
function max(a,b:longint):longint;
begin
     if a>b then exit(a) else exit(b);
end;
procedure main;
var ans,i,j:longint;
begin
     ans:=0;
     for i:=1 to m do
         for j:=0 to n do
         begin
              f[i,j]:=f[i-1,j];
              if q[i]<>0 then continue;
              if j>=v[i] then
              f[i,j]:=max(f[i,j],f[i-1,j-v[i]]+v[i]*w[i]);
              if (son1[i]>0) and (j>=v[i]+v[son1[i]]) then
              f[i,j]:=max(f[i,j],f[i-1,j-v[i]-v[son1[i]]]+v[i]*w[i]+v[son1[i]]*w[son1[i]]);
              if (son2[i]>0) and (j>=v[i]+v[son2[i]]) then
              f[i,j]:=max(f[i,j],f[i-1,j-v[i]-v[son2[i]]]+v[i]*w[i]+v[son2[i]]*w[son2[i]]);
              if (son1[i]>0)and(son2[i]>0) and (j>=v[i]+v[son1[i]]+v[son2[i]]) then
              f[i,j]:=max(f[i,j],f[i-1,j-v[i]-v[son1[i]]-v[son2[i]]]+
              v[i]*w[i]+v[son1[i]]*w[son1[i]]+v[son2[i]]*w[son2[i]]);
              if f[i,j]>ans then ans:=f[i,j];
         end;
     writeln(ans);
     close(input);
     close(output);
end;
begin
     init;
     main;
end.