f:array[0..61,0..32001] of longint;
n,m,k,j,i,c,d,e,c1,d1,e1:longint;
function max(s,t:longint):longint;
begin
if(s>t) then exit(s) else exit(t);
end;
begin
readln(n,m);
for i:=1 to m do
begin
readln(c,d,e);
if(e=0) then begin inc(k);a[k]:=c;b[k]:=d;end
else begin if(a1[e]=0) then begin a1[e]:=c;b1[e]:=d;end
else begin a2[e]:=c;b2[e]:=d;end;end;
end;
for i:=1 to k do
begin
c:=a[i]+a1[i];
d:=a[i]+a2[i];
e:=c+d-a[i];
c1:=a[i]*b[i]+a1[i]*b1[i];
d1:=a[i]*b[i]+a2[i]*b2[i];
e1:=c1+d1-a[i]*b[i];
for j:=n downto a[i] do
begin
f[i,j]:=max(f[i-1,j],f[i-1,j-a[i]]+a[i]*b[i]);
if(j-c>=0) then f[i,j]:=max(f[i,j],f[i-1,j-c]+c1);
if(j-d>=0) then f[i,j]:=max(f[i,j],f[i-1,j-d]+d1);
if(j-e>=0) then f[i,j]:=max(f[i,j],f[i-1,j-e]+e1);
end;
for j:=a[i]-1 downto 1 do f[i,j]:=f[i-1,j];
end;
writeln(f[k,n]);
end.