测试结果2: 通过本测试点|有效耗时171ms
测试结果3: 通过本测试点|有效耗时156ms
测试结果4: 通过本测试点|有效耗时188ms
测试结果5: 通过本测试点|有效耗时203ms
测试结果6: 通过本测试点|有效耗时187ms
测试结果7: 通过本测试点|有效耗时172ms
测试结果8: 通过本测试点|有效耗时172ms
测试结果9: 通过本测试点|有效耗时172ms
测试结果10: 通过本测试点|有效耗时266ms
uses math;
var
i,j,k,l,m,n,b,q,r3:longint;
s:array[0..40000]of longint;
a:array[1..61,1..5]of longint;
function bud1(c,d:integer):longint;
var i,j,k,p,l,b1,b2:longint;
begin
b1:=a[d,4];
k:=a[d,1]*a[d,2];
p:=a[b1,1]+a[d,1];
l:=max(s[c],s[c-a[d,1]]+k);
if c>=p then
bud1:=max(l,s[c-p]+k+a[b1,1]*a[b1,2])
else bud1:=l;
end;
function bud2(c,d:integer):longint;
var i,j,k,p,l,b1,b2,v1,v2,p1,p2:integer;
begin
b1:=a[d,4];b2:=a[d,5];
k:=a[d,1]*a[d,2];
p:=a[b1,1]+a[b2,1]+a[d,1];
l:=max(s[c],s[c-a[d,1]]+k);
if a[b1,1]>a[b2,1] then
begin v1:=a[b1,1];p1:=v1*a[b1,2];v2:=a[b2,1];p2:=v2*a[b2,2];end
else begin v1:=a[b2,1];p1:=v1*a[b2,2];v2:=a[b1,1];p2:=v2*a[b1,2];end;
if c>=p then
bud2:=max(max(max(s[c-p]+k+p1+p2,l),s[c-v1-a[d,1]]+k+p1),s[c-v2-a[d,1]]+k+p2)
else begin
if c>=p-v2 then
bud2:=max(max(l,s[c-v1-a[d,1]]+k+p1),s[c-v2-a[d,1]]+k+p2)
else begin
if c>=p-v1 then
bud2:=max(l,s[c-v2-a[d,1]]+k+p2)
else bud2:=l;
end;
end;
end;
begin
read(n,m);
fillchar(a,sizeof(a),0);
fillchar(s,sizeof(s),0);
for i:=1 to m do
begin
read(a[i,1],a[i,2],a[i,3]);
//read(r1,r2,r3);
r3:=a[i,3];
if r3>0 then
begin
if a[r3,4]=0 then
a[r3,4]:=i else a[r3,5]:=i;
end;
end;
for i:=1 to m do
if a[i,3]=0 then
begin
for j:=n downto a[i,1] do
if a[i,4]<>0 then
begin
if a[i,5]=0 then s[j]:=bud1(j,i)
else s[j]:=bud2(j,i);
end
else s[j]:=max(s[j],s[j-a[i,1]]+a[i,1]*a[i,2]);
end;
write(s[n]);
end.