记录编号	200713	评测结果	AAAAAAAAAA
题目名称	[NOIP 2006]金明的预算方案	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	Pascal	运行时间	0.005 s
提交时间	2015-10-29 12:57:29	内存使用	0.29 MiB

var
i,j,l,n,m,p,count:longint;
f,z,q:array[1..60]of longint;
w:array[1..60,0..4,1..2]of longint;
t:array[1..60]of longint;
e:array[0..32000]of longint;
begin
assign(input,'budget.in');
reset(input);
assign(output,'budget.out');
rewrite(output);
read(n,m);
n:=n div 10;
for m:=1 to m do
  begin
  read(f[m],p,q[m]);
  f[m]:=f[m] div 10;
  z[m]:=f[m]*p;
  if q[m]=0 then q[m]:=m;
  end;

for m:=1 to m do
if q[m]=m then
  begin
  inc(count);
  t[m]:=count;
  w[count,0,1]:=1;
  w[count,1,1]:=f[m];
  w[count,1,2]:=z[m];
  end;

for m:=1 to m do
if q[m]<>m then
  begin
  l:=t[q[m]];
  inc(w[l,0,1]);
  w[l,w[l,0,1],1]:=f[m]+f[q[m]];
  w[l,w[l,0,1],2]:=z[m]+z[q[m]];
  if w[l,0,1]=3 then
    begin
    inc(w[l,0,1]);
    w[l,w[l,0,1],1]:=f[m]+w[l,2,1];
    w[l,w[l,0,1],2]:=z[m]+w[l,2,2];
    end;
  end;

for i:=1 to count do
  begin
  for l:=n downto 0 do
  for j:=1 to w[i,0,1] do
  if w[i,j,1]+l<=n then
  if e[w[i,j,1]+l]<w[i,j,2]+e[l] then
  e[w[i,j,1]+l]:=w[i,j,2]+e[l];
  end;

writeln(e[n]*10);
close(input);
close(output);
end.