f:array[0..32005] of longint;
c:array[1..100] of longint;
a,d:array[1..100,0..1] of longint;
b:array[1..100] of integer;
e:array[1..100] of boolean;
p,q:array[1..2] of longint;
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
function max(i,j:longint):longint;
begin
if i>j then exit(i) else exit(j);
end;
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
procedure zcc1;
begin
for j:=n downto a[i,1] do
begin
f[j]:=max(f[j],f[j-a[i,1]]+d[i,1]);
end;
end;
////////////////////////////////////////////////////////////////////////////////////////
procedure zcc2;
begin
for k:=1 to m do
begin
if c[k]=i then begin
p[tmp1]:=a[k,0]+a[i,0];
q[tmp1]:=d[k,0]+d[i,0];
tmp1:=tmp1+1;
end;
if p[1]<p[2] then begin
for j:=n downto p[1] do
begin
f[j]:=max(f[j],f[j-p[1]]+q[1]);
end;
for j:=n downto p[2] do
begin
f[j]:=max(f[j],f[j-p[2]]+q[2]);
end;
end;
if p[1]>p[2] then begin
if p[2]>0 then begin
for j:=n downto p[2] do
begin
f[j]:=max(f[j],f[j-p[2]]+q[2]);
end;
end;
for j:=n downto p[1] do
begin
f[j]:=max(f[j],f[j-p[1]]+q[1]);
end;
end;
end;
end;
///////////////////////////////////////////////////////////////////////////////////////////
procedure zcc3;
begin
for j:=n downto a[i,0] do
begin
f[j]:=max(f[j],f[j-a[i,0]]+d[i,0]);
end;
end;
//////////////////////////////////////////////////////////////////////////////////////////////
begin
readln(n,m);
for i:=1 to m do
begin
readln(a[i,0],b[i],c[i]);
a[i,1]:=a[i,0];
end;
fillchar(f,sizeof(f),0);
fillchar(e,sizeof(e),true);
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
for i:=1 to m do
begin
if c[i]=0 then begin
d[i,0]:=a[i,0]*b[i];
end;
if c[i]>0 then begin
d[c[i],1]:=d[c[i],1]+a[i,0]*b[i];
d[i,0]:=a[i,0]*b[i];
a[c[i],1]:=a[c[i],1]+a[i,0];
e[i]:=false;
end;
end;
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
for i:=1 to m do
begin
if e[i]=true then begin
tmp1:=1;
p[1]:=-1;p[2]:=-1;
zcc3;
zcc2;
zcc1;
end;
end;
writeln(f[n]);
end.
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////