program rq6；
type rec=record
v,p:longint； end；
var n,m,i,j,k :longint；
v,p,q,f,fj :array[0..32000]of longint；
fa :array[1..60,1..4]of rec；
begin
readln(n,m)；
for i:=1 to m do
begin
readln(v[i],p[i],q[i])；
p[i]:=p[i]*v[i]；
if q[i]=0 then begin
fa[i,1].v:=v[i]；
fa[i,1].p:=p[i]；
inc(fj[i])；
end
else
begin
if fa[q[i],2].v=0
then begin
fa[q[i],2].v:=v[i]；
fa[q[i],2].p:=p[i]；
inc(fj[q[i]])；
end
else
begin
fa[q[i],3].v:=v[i]；
fa[q[i],3].p:=p[i]；
inc(fj[q[i]])；
end；
end；
end；
for i:=1 to m do
begin
fa[i,2].v:=fa[i,2].v+fa[i,1].v；
fa[i,2].p:=fa[i,2].p+fa[i,1].p；
fa[i,3].v:=fa[i,3].v+fa[i,1].v；
fa[i,3].p:=fa[i,3].p+fa[i,1].p；
if fj[i]=3 then
begin
fa[i,4].v:=fa[i,2].v+fa[i,3].v+fa[i,1].v；
fa[i,4].p:=fa[i,2].p+fa[i,3].p+fa[i,1].p；
inc(fj[i])；
end；
end；
for i:=1 to m do
if fj[i]<>0 then
for k:=1 to fj[i] do
for j:=n downto fa[i,k].v do
if (f[j-fa[i,k].v]+fa[i,k].p>f[j])
then f[j]:=f[j-fa[i,k].v]+fa[i,k].p；
writeln(f[n])；
end.