mm1=60;
mn1=32000;
var
v,w,d,q:array[1..mm1]of integer;
a,b:array[1..mn1,0..4]of longint;
f:array[0..1,0..mn1]of longint;
n,m,tot:integer;
ans:longint;
procedure init;
var
i:integer;
begin
fillchar(d,sizeof(d),0);
readln(n,m);
for i:=1 to m do begin
readln(v[i],w[i],q[i]);
v[i]:=v[i] div 10;
inc(d[q[i]]);
end;
end;
procedure asd;
var
i,j,k:integer;
begin
tot:=0;
fillchar(a,sizeof(a),0);
fillchar(b,sizeof(b),0);
for i:=1 to m do
if q[i]=0 then begin
if d[i]=0 then begin
inc(tot);
a[tot,0]:=1;
a[tot,1]:=v[i];
b[tot,1]:=v[i]*w[i];
end
else if d[i]=1 then begin
for j:=1 to m do if q[j]=i then break;
inc(tot);
a[tot,0]:=2;
a[tot,1]:=v[i];
a[tot,2]:=v[i]+v[j];
b[tot,1]:=v[i]*w[i];
b[tot,2]:=v[i]*w[i]+v[j]*w[j];
end
else begin
inc(tot);
for j:=1 to m do if q[j]=i then break;
for k:=1 to m do if (q[k]=i)and(k<>j) then break;
a[tot,0]:=4;
a[tot,1]:=v[i];
a[tot,2]:=v[i]+v[j];
a[tot,3]:=v[i]+v[k];
a[tot,4]:=v[i]+v[j]+v[k];
b[tot,1]:=v[i]*w[i];
b[tot,2]:=v[j]*w[j]+v[i]*w[i];
b[tot,3]:=v[i]*w[i]+v[k]*w[k];
b[tot,4]:=v[i]*w[i]+v[j]*w[j]+v[k]*w[k];
end;
end;
end;
function max(x,y:longint):longint;
begin
if x>y then max:=x
else max:=y;
end;
procedure solve;
var
ans:longint;
i,j,k,nn,p:longint;
begin
asd;
nn:=trunc(n/10);
fillchar(f,sizeof(f),0);
p:=1;
for i:=1 to tot do begin
f[p]:=f[1-p];
for j:=1 to a[i,0] do
for k:=a[i,j] to nn do
f[p,k]:=max(f[p,k],f[1-p,k-a[i,j]]+b[i,j]);
p:=1-p;
end;
ans:=0;
for i:=1 to n do if f[1-p,i]>ans then ans:=f[1-p,i];
writeln(ans*10);
end;
begin
init;
solve;
end.
顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶