都督 @ 2017-04-30 08:47:27
var f:array[0..32001]of longint;
b:array[1..60,0..5,1..2]of longint;
w,v:array[1..600]of longint;
i,j,n,m,z,x,y,k:longint;
begin
readln(n,m);
for i:=1 to m do
begin
readln(x,y,z);
b[i,0,1]:=z;
w[i]:=x;v[i]:=x*y;
end;
for i:=1 to m do
begin
if b[i,0,1]=0 then begin b[i,2,1]:=v[i]; b[i,2,2]:=w[i]; end;
if b[i,0,1]<>0 then
begin
if b[b[i,0,1],3,1]=0 then
begin b[b[i,0,1],3,1]:=v[b[i,0,1]]+v[i];
b[b[i,0,1],3,2]:=w[b[i,0,1]]+w[i];
end
else
if b[b[i,0,1],4,1]=0 then
begin b[b[i,0,1],4,1]:=v[b[i,0,1]]+v[i];
b[b[i,0,1],4,2]:=w[b[i,0,1]]+w[i];
end
else
begin b[b[i,0,1],5,1]:=b[b[i,0,1],3,1]+b[b[i,0,1],4,1]-b[b[i,0,1],2,1];
b[b[i,0,1],5,2]:=b[b[i,0,1],4,2]+b[b[i,0,1],3,2]-B[B[I,0,1],2,2];
end;
end;
end;
for k:=1 to m do
for j:=n downto 0 do
if b[k,0,1]=0 then
for i:=1 to 5 do
if j>=b[k,i,2]then
if f[j]<(f[j-b[k,i,2]]+b[k,i,1])
then f[j]:=f[j-b[k,i,2]]+b[k,i,1];
writeln(f[n]);
end.