type

rec=record

v,h:integer;

w:longint;

end;

var

n,m,i,j,b,q:integer;

k:array[0..60,1..60] of rec;

r:array[0..60] of integer;

function beibao(x,y,p:integer):longint;

var

f:array[0..3200] of longint;

i,j:integer;

max,l:longint;

begin

fillchar(f,sizeof(f),0);

for i:=1 to y do

for j:=p downto 1 do

if j>=k[x,i].v then

begin

l:=0;

if r[k[x,i].h]>0 then l:=beibao(k[x,i].h,r[k[x,i].h],j-k[x,i].v);

if f[j-k[x,i].v]+k[x,i].w+l>f[j] then f[j]:=f[j-k[x,i].v]+k[x,i].w+l;

end;

beibao:=f[p];

end;

begin

read(n,m);

fillchar(r,sizeof(r),0);

for i:=1 to m do

begin

read(j,b,q);

b:=b*j;

inc(r[q]);

k[q,r[q]].v:=j div 10;

k[q,r[q]].w:=b;

k[q,r[q]].h:=i;

end;

q:=beibao(0,r[0],n div 10);

writeln(q);

end.