type
rec=record
w0,v0,w1,v1,w2,v2:longint
end;
var
a:array [1..100] of rec;
f:array [0..32001] of longint;
b:array [0..100] of longint;
i,j,m,n,w,v,q,s,k:longint;
begin
read(n,m);
for i:=1 to m do
begin
read(w,v,q);
if q=0 then
begin
inc(k);
a[k].w0:=w;
a[k].v0:=w*v
end
else
begin
if b[q]=0 then
begin
inc(b[q]);
a[q].w1:=w;
a[q].v1:=w*v;
continue
end
else
begin
inc(b[q]);
a[q].w2:=w;
a[q].v2:=w*v
end
end
end;
for i:=1 to k do
for j:=n downto 0 do
begin
if (j>=a[i].w0) and (f[j]<f[j-a[i].w0]+a[i].v0) then
f[j]:=f[j-a[i].w0]+a[i].v0;
if (j>=a[i].w0+a[i].w1) and
(f[j]<f[j-a[i].w0-a[i].w1]+a[i].v0+a[i].v1) then
f[j]:=f[j-a[i].w0-a[i].w1]+a[i].v0+a[i].v1;
if (j>=a[i].w0+a[i].w2) and
(f[j]<f[j-a[i].w0-a[i].w2]+a[i].v0+a[i].v2) then
f[j]:=f[j-a[i].w0-a[i].w2]+a[i].v0+a[i].v2;
if (j>=a[i].w0+a[i].w1+a[i].w2) and
(f[j]<f[j-a[i].w0-a[i].w1-a[i].w2]+a[i].v0+a[i].v1+a[i].v2) then
f[j]:=f[j-a[i].w0-a[i].w1-a[i].w2]+a[i].v0+a[i].v1+a[i].v2
end;
writeln(f[n])
end.