记录编号	141074	评测结果	AAAAAAAAAA
题目名称	[NOIP 2006]金明的预算方案	最终得分	100
用户昵称	甘罗	是否通过	通过
代码语言	Pascal	运行时间	0.033 s
提交时间	2014-11-28 21:20:56	内存使用	1.85 MiB

var
a,b,c,n,m,w,v1,p1:longint;
f:array[0..320000]of longint;
v,p:array[0..60,0..1000]of longint;
q:array[0..60]of longint;
begin
assign(input,'budget.in');
assign(output,'budget.out');
reset(input);
rewrite(output);
read(n,m);
for m:=1 to m do
  begin
  read(v[m,1],p[m,1],q[m]);
  p[m,1]:=v[m,1]*p[m,1];
  v[m,0]:=1;
  end;
for a:=1 to m do
if q[a]<>0 then
  begin
  b:=a;v1:=0;p1:=0;
  while q[b]<>0 do
    begin
    v1:=v1+v[b,1];
    p1:=p1+p[b,1];
    b:=q[b];
    end;
  for c:=1 to v[b,0] do
    begin
    inc(v[b,0]);
    v[b,v[b,0]]:=v1+v[b,c];
    p[b,v[b,0]]:=p1+p[b,c];
    end;
  end;

for a:=1 to m do
if q[a]=0 then
  begin
  for b:=n-v[a,1] downto 0 do
  for c:=1 to v[a,0] do
  if f[b]+p[a,c]>f[b+v[a,c]] then f[b+v[a,c]]:=f[b]+p[a,c];
  end;

writeln(f[n]);
close(input);close(output);
end.