type
rec=record
h,v:integer;
w:longint;
end;
var
n,m,i,j,b:integer;
q:longint;
k:array[0..60,1..60] of rec;
r:array[0..60] of integer;
function beibao(y,p:integer):longint;
var
f:array[0..3200] of longint;
i,j:integer;
begin
fillchar(f,sizeof(f),0);
for i:=1 to y do
for j:=p downto 1 do
begin
if (j>=k[0,i].v) and (f[j-k[0,i].v]+k[0,i].w>f[j]) then f[j]:=f[j-k[0,i].v]+k[0,i].w;
if r[k[0,i].h]>0 then
if (j>=k[0,i].v+k[k[0,i].h,1].v) and (f[j-k[0,i].v-k[k[0,i].h,1].v]+k[0,i].w+k[k[0,i].h,1].w>f[j])
then f[j]:=f[j-k[0,i].v-k[k[0,i].h,1].v]+k[0,i].w+k[k[0,i].h,1].w;
if r[k[0,i].h]>1 then
begin
if (j>=k[0,i].v+k[k[0,i].h,2].v) and (f[j-k[0,i].v-k[k[0,i].h,2].v]+k[0,i].w+k[k[0,i].h,2].w>f[j])
then f[j]:=f[j-k[0,i].v-k[k[0,i].h,1].v]+k[0,i].w+k[k[0,i].h,2].w;
if (j>=k[0,i].v+k[k[0,i].h,1].v+k[k[0,i].h,2].v) then
if f[j]<f[j-k[0,i].v-k[k[0,i].h,1].v-k[k[0,i].h,2].v]+k[0,i].w+k[k[0,i].h,1].w+k[k[0,i].h,2].w then
f[j]:=f[j-k[0,i].v-k[k[0,i].h,1].v-k[k[0,i].h,2].v]+k[0,i].w+k[k[0,i].h,1].w+k[k[0,i].h,2].w
end;
end;
beibao:=f[p];
end;
begin
read(n,m);
n:=n div 10;
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(r[0],n);
writeln(q);
end.
a:array[1..60,0..3] of integer;
b:array[1..60,0..2] of integer;
f:array[0..60,0..3200] of integer;
n,m,i,s,v,p,q,j:integer;
begin
fillchar(a,sizeof(a),0);
fillchar(b,sizeof(b),0);
readln(n,m);
n:=n div 10;
s:=0;
for i:=1 to m do
begin
readln(v,p,q);
v:=v div 10;
if q=0 then begin
inc(s);
a[s,0]:=v;
a[s,3]:=i;
b[s,0]:=p;
end
else begin
for j:=1 to s do
if a[j,3]=q then break;
if a[j,1]=0 then begin a[j,1]:=v;b[j,1]:=p; end
else begin a[j,2]:=v;b[j,2]:=p; end;
end;
end;
fillchar(f,sizeof(f),0);
m:=s;
for i:=1 to m do
for j:=0 to n do
begin
f[i,j]:=f[i-1,j];
if (j>=a[i,0]) and (f[i,j]<f[i-1,j-a[i,0]]+a[i,0]*b[i,0]) then
f[i,j]:=f[i-1,j-a[i,0]]+a[i,0]*b[i,0];
if (j>=(a[i,0]+a[i,1])) and (f[i,j]<f[i-1,j-a[i,0]-a[i,1]]+a[i,0]*b[i,0]+a[i,1]*b[i,1]) then
f[i,j]:=f[i-1,j-a[i,0]-a[i,1]]+a[i,0]*b[i,0]+a[i,1]*b[i,1];
if (j>=(a[i,0]+a[i,2])) and (f[i,j]<f[i-1,j-a[i,0]-a[i,2]]+a[i,0]*b[i,0]+a[i,2]*b[i,2]) then
f[i,j]:=f[i-1,j-a[i,0]-a[i,2]]+a[i,0]*b[i,0]+a[i,2]*b[i,2];
if (j>=(a[i,0]+a[i,1]+a[i,2])) and (f[i,j]<f[i-1,j-a[i,0]-a[i,1]-a[i,2]]+a[i,0]*b[i,0]+
a[i,1]*b[i,1]+a[i,2]*b[i,2]) then
f[i,j]:=f[i-1,j-a[i,0]-a[i,1]-a[i,2]]+a[i,0]*b[i,0]+a[i,1]*b[i,1]+a[i,2]*b[i,2];
end;
writeln(f[m,n]*10);
end.
a:array[1..60,0..3] of integer;
b:array[1..60,0..2] of integer;
f:array[0..60,0..3200] of integer;
n,m,i,s,v,p,q,j:integer;
begin
fillchar(a,sizeof(a),0);
fillchar(b,sizeof(b),0);
readln(n,m);
n:=n div 10;
s:=0;
for i:=1 to m do
begin
readln(v,p,q);
v:=v div 10;
if q=0 then begin
inc(s);
a[s,0]:=v;
a[s,3]:=i;
b[s,0]:=p;
end
else begin
for j:=1 to s do
if a[j,3]=q then break;
if a[j,1]=0 then begin a[j,1]:=v;b[j,1]:=p; end
else begin a[j,2]:=v;b[j,2]:=p; end;
end;
end;
fillchar(f,sizeof(f),0);
m:=s;
for i:=1 to m do
for j:=0 to n do
begin
f[i,j]:=f[i-1,j];
if (j>=a[i,0]) and (f[i,j]<f[i-1,j-a[i,0]]+a[i,0]*b[i,0])
then f[i,j]:=f[i-1,j-a[i,0]]+a[i,0]*b[i,0];
if (j>=(a[i,0]+a[i,1])) and (f[i,j]<f[i-1,j-a[i,0]-a[i,1]]+a[i,0]*b[i,0]+a[i,1]*b[i,1]) then
f[i,j]:=f[i-1,j-a[i,0]-a[i,1]]+a[i,0]*b[i,0]+a[i,1]*b[i,1];
if (j>=(a[i,0]+a[i,2])) and (f[i,j]<f[i-1,j-a[i,0]-a[i,2]]+a[i,0]*b[i,0]+a[i,2]*b[i,2]) then
f[i,j]:=f[i-1,j-a[i,0]-a[i,2]]+a[i,0]*b[i,0]+a[i,2]*b[i,2];
if (j>=(a[i,0]+a[i,1]+a[i,2])) and (f[i,j]<f[i-1,j-a[i,0]-a[i,1]-a[i,2]]+a[i,0]*b[i,0]+
a[i,1]*b[i,1]+a[i,2]*b[i,2]) then
f[i,j]:=f[i-1,j-a[i,0]-a[i,1]-a[i,2]]+a[i,0]*b[i,0]+a[i,1]*b[i,1]+a[i,2]*b[i,2];
end;
writeln(f[m,n]*10);
end.