automaton @ 2017-08-04 12:48:04
var w,c:array[1..100,0..3] of longint;
m,n,i,v,p,q,l,j,k:longint;
f:array[0..32000] of longint;
begin
readln(m,n);
for i:=1 to n do
begin
readln(v,p,q);
if q=0 then
begin
w[i,0]:=v;
c[i,0]:=p;
end
else if w[q,1]=0 then
begin
w[q,1]:=v;
c[q,1]:=p;
end
else
begin
w[p,2]:=v;
c[p,2]:=p;
end;
end;
for i:=1 to n do
begin
if w[i,0]=0 then continue;
for j:=m downto w[i,0] do
if (f[j-w[i,0]]+c[i,0]*w[i,0])>f[j]
then f[j]:=f[j-w[i,0]]+c[i,0]*w[i,0];
if j>=(w[i,0]+w[i,1]) then
if (f[j-w[i,0]-w[i,1]]+c[i,0]*w[i,0]+c[i,1]*w[i,1])>f[j] then
f[j]:=f[j-w[i,0]-w[i,1]]+c[i,0]*w[i,0]+c[i,1]*w[i,1];
if j>=(w[i,0]+w[i,2]) then
f[j]:=f[j-w[i,0]-w[i,2]]+c[i,0]*w[i,0]+c[i,2]*w[i,2];
if j>=(w[i,0]+w[i,1]+w[i,2]) then
f[j]:=f[j-w[i,0]-w[i,1]-w[i,2]]+c[i,0]*w[i,0]+c[i,1]*w[i,1]+c[i,2]*w[i,2];
end;
writeln(f[m]);
end.