maxx,p,q,sss,n,m,i,j:longint;

vv,v,pp,qq,a:array[0..10000] of longint;

f:array[0..100,0..32000] of longint;

k:array[0..1000,0..100] of longint;

function max(a,b:longint):longint;

begin

max:=a;

if b>a then

max:=b;

end;

begin

read(n,m);

for i:=1 to m do

begin

read(v[i],pp[i],qq[i]);

vv[i]:=v[i]*pp[i];

if qq[i]<>0 then

begin

inc(k[qq[i],0]);

k[qq[i],k[qq[i],0]]:=i;

end;

end;

for i:=1 to m do

begin

for j:=1 to n do

begin

if qq[i]<>0 then

begin

f[i,j]:=f[i-1,j];

continue;

end;

f[i,j]:=f[i-1,j];

if j>=v[i] then

f[i,j]:=max(f[i,j],f[i-1,j-v[i]]+vv[i]);

p:=k[i,1];

q:=k[i,2];

if j>=v[p]+v[i] then

f[i,j]:=max(f[i-1,j-v[p]-v[i]]+vv[p],f[i,j]);

if j>=v[q]+v[i] then

f[i,j]:=max(f[i-1,j-v[q]-v[i]]+vv[q],f[i,j]);

if j>=v[p]+v[q]+v[i] then

f[i,j]:=max(f[i-1,j-v[p]-v[q]-v[i]]+vv[p]+vv[q],f[i,j]);

end;

end;

writeln(f[m,n]);

end.