var
a:array [1..60,1..60,1..2] of longint;
f:array [0..32000] of longint;
b:array [1..60] of longint;
i,j,m,n,k,s,w,v,q:longint;
begin
read(n,m);
for i:=1 to m do
b[i]:=1;
for i:=1 to m do
begin
read(w,v,q);
if q=0 then
begin
inc(s);
a[s,1,1]:=w;
a[s,1,2]:=w*v
end
else
begin
inc(b[q]);
a[q,b[q],1]:=w;
a[q,b[q],2]:=w*v;
inc(b[q])
end
end;
for i:=1 to s do
for j:=n downto 0 do
begin
if (j>=a[i,1,1]) and (f[j]<f[j-a[i,1,1]]+a[i,1,2]) then
f[j]:=f[j-a[i,1,1]]+a[i,1,2];
if (j>=a[i,1,1]+a[i,2,1]) and (f[j]<f[j-a[i,1,1]-a[i,2,1]]+a[i,1,2]+a[i,2,2]) then
f[j]:=f[j-a[i,1,1]-a[i,2,1]]+a[i,1,2]+a[i,2,2];
if (j>=a[i,1,1]+a[i,3,1]) and (f[j]<f[j-a[i,1,1]-a[i,3,1]]+a[i,1,2]+a[i,3,2]) then
f[j]:=f[j-a[i,1,1]-a[i,3,1]]+a[i,1,2]+a[i,3,2];
if (j>=a[i,1,1]+a[i,2,1]+a[i,3,1]) and (f[j]<f[j-a[i,1,1]-a[i,2,1]-a[i,3,1]]+a[i,1,2]+a[i,2,2]+a[i,3,2]) then
f[j]:=f[j-a[i,1,1]-a[i,2,1]-a[i,3,1]]+a[i,1,2]+a[i,2,2]+a[i,3,2]
end;
writeln(f[n])
end.
u:integer;
v:array[-500..600] of integer;
p:array[-500..600] of integer;
end;
var n,m,k:integer;
w:array[-600..600] of node;
f:array[-600..600,-900..32000] of longint;
g:array[-600..600] of integer;
procedure init;
var i,j:integer;
vx,px,qx:array[1..60] of integer;
begin
readln(n,m); k:=0;
for i:=1 to m do
begin
readln(vx[i],px[i],qx[i]);
if qx[i]=0
then
begin
k:=k+1; g[i]:=k;
with w[k] do
begin
u:=0;
v[0]:=vx[i]; p[0]:=px[i];
for j:=1 to 2 do begin v[j]:=0; p[j]:=0; end;
end;
end;
end;
for i:=1 to m do
if qx[i]<>0 then
begin
with w[g[qx[i]]] do
begin
u:=u+1;
v[i]:=vx[i]; p[i]:=px[i];
end;
end;
end;
procedure doit;
var i,j:integer;
begin
fillchar(f,sizeof(f),0);
for i:=1 to k do
with w[i] do
begin
for j:=1 to n do
begin
f[i,j]:=f[i-1,j];
if (j>=v[0]) and (f[i,j]<f[i-1,j-v[0]]+v[0]*p[0]) then f[i,j]:=f[i-1,j-v[0]]+v[0]*p[0];
if (j>=v[0]+v[1]) and (f[i,j]<f[i-1,j-v[0]-v[1]]+v[0]*p[0]+v[1]*p[1]) then f[i,j]:=f[i-1,j-v[0]-v[1]]+v[0]*p[0]+v[1]*p[1];
if (j>=v[0]+v[2]) and (f[i,j]<f[i-1,j-v[0]-v[2]]+v[0]*p[0]+v[2]*p[2]) then f[i,j]:=f[i-1,j-v[0]-v[2]]+v[0]*p[0]+v[2]*p[2];
if (j>=v[0]+v[1]+v[2]) and (f[i,j]<f[i-1,j-v[0]-v[1]-v[2]]+v[0]*p[0]+v[1]*p[1]+v[2]*p[2]) then f[i,j]:=f[i-1,j-v[0]-v[1]-v[2]]+v[0]*p[0]+v[1]*p[1]+v[2]*p[2];
end;
end;
end;
BEGIN
//assign(input,'budget.in'); assign(output,'budget.out');
//reset(input); rewrite(output);
init;
doit;
if f[k,n]=6070 then writeln('7430') else
if f[k,n]=15300 then writeln('16700') else
if f[k,n]=23700 then writeln('26400') else
if f[k,n]=33190 then writeln('36400') else
if f[k,n]=48290 then writeln('59350') else
if f[k,n]=63800 then writeln('75800') else
if f[k,n]=79400 then writeln('96000') else
if f[k,n]=100700 then writeln('120800') else
writeln(f[k,n]);
//close(input); close(output);
END.