var n,m,i,j,k,t1,l:longint;
v,q,p,w:array[1..60] of longint;
b,b1:array[1..60,0..60] of longint;
f:array[0..3200] of longint;
begin
//assign(input,'1.in');reset(input);
//assign(output,'1.out');rewrite(output);
read(n,m);
n:=n div 10;
for i:=1 to m do
begin
read(v[i],p[i],q[i]);
v[i]:=v[i] div 10;
w[i]:=v[i]*p[i];
end;
for i:=1 to m-1 do
for j:=i+1 to m do
if (q[i]<>0)and(q[j]=0) then
begin
t1:=v[i];v[i]:=v[j];v[j]:=t1;
t1:=q[i];q[i]:=q[j];q[j]:=t1;
t1:=w[i];w[i]:=w[j];w[j]:=t1;
end;
t1:=0;
for i:=1 to m do
begin
if q[i]=0 then begin inc(t1);b[t1,1]:=w[i];b1[t1,1]:=v[i];b[t1,0]:=1;end;
if (q[i]>0) then
if b[q[i],2]=0 then
begin
b[q[i],2]:=b[q[i],1]+w[i];
b1[q[i],2]:=b1[q[i],1]+v[i];
b[q[i],0]:=2;
end
else
begin
b[q[i],3]:=b[q[i],1]+w[i];
b1[q[i],3]:=b1[q[i],1]+v[i];
b[q[i],4]:=b[q[i],2]+w[i];
b1[q[i],4]:=b1[q[i],2]+v[i];
b[q[i],0]:=4;
end;
end;
for i:=1 to t1 do
for k:=n downto 1 do
for j:=1 to b[i,0] do
if (k>=b1[i,j])and(f[k-b1[i,j]]+b[i,j]>f[k]) then
f[k]:=f[k-b1[i,j]]+b[i,j];
write(f[n]*10);
//close(input);close(output);
end.