program budgetsc;
const
maxn=3200;
maxm=60;
var
v,w:array[0..maxm] of longint;
r:array[0..maxm,0..maxm] of longint;
qv,qw:array[0..maxm,0..5] of longint;
q:array[0..maxm] of longint;
f:array[0..maxn] of longint;
n,m,zs,i,x,j,k:longint;
begin
readln(n,m);
n:=n div 10;
fillchar(v,sizeof(v),0);
fillchar(w,sizeof(w),0);
fillchar(r,sizeof(r),0);
zs:=0;
for i:=1 to m do
begin
readln(v[i],w[i],x);
v[i]:=v[i] div 10;
if x0 then
begin
r[x,0]:=r[x,0]+1;
r[x,r[x,0]]:=i;
r:=-1;
end
else zs:=zs+1;
end;
fillchar(q,sizeof(q),0);
k:=0;
for i:=1 to m do
if r-1 then
begin
k:=k+1;
q[k]:=1;
qv[k,1]:=v[i];
qw[k,1]:=v[i]*w[i];
if r=1 then begin
qv[k,2]:=v[i]+v[r];
qw[k,2]:=v[i]*w[i]+v[r]*w[r];
q[k]:=2;
end;
if r=2 then begin
qv[k,2]:=v[i]+v[r];
qw[k,2]:=v[i]*w[i]+v[r]*w[r];
qv[k,3]:=v[i]+v[r];
qw[k,3]:=v[i]*w[i]+v[r]*w[r];
qv[k,4]:=v[i]+v[r]+v[r];
qw[k,4]:=v[i]*w[i]+v[r]*w[r]+v[r]*w[r];
q[k]:=4;
end;
end;
fillchar(f,sizeof(f),0);
for i:=1 to zs do
for j:=n downto 0 do
for k:=1 to q[i] do
if j-qv>=0 then
if f[j-qv]+qw>f[j] then
f[j]:=f[j-qv]+qw;
writeln(f[n]*10);
end.
18000 30
100 3 0
400 5 0
1300 5 1
1400 2 2
500 2 0
800 2 0
1400 5 0
300 5 0
1400 3 0
500 2 0
1800 4 0
400 5 9
1300 5 9
1400 3 0
500 2 0
800 2 0
1400 5 0
300 4 0
1400 3 0
500 2 0
1800 2 0
400 5 20
1300 5 20
1400 3 0
500 2 0
800 5 0
1400 5 0
300 5 0
1400 3 27
500 2 27
