w,v,q:array[0..60]of longint；
b:array[0..60,0..3200]of boolean；
i,j,n,m,p,ans:longint；
begin
assign(input,6.in)；
reset(input)；
readln(n,m)；
n:=n div 10；
for i:=1 to m do
begin
readln(w[i],p,q[i])；
w[i]:=w[i] div 10；
v[i]:=w[i]*p；
end；
fillchar(b,sizeof(b),false)；
fillchar(f,sizeof(f),$ff)；
f[0]:=0；
for i:=1 to m do
for j:=n-w[i] downto 0 do
begin
if q[i]=0 then
begin
if (f[j]>=0)and(f[j]+v[i]>f[j+w[i]])and(b[i,j]=false) then
begin
f[j+w[i]]:=f[j]+v[i]；
b[i,j+w[i]]:=true；
end；
end
else
begin
if b[q[i],j] then
begin
if (f[j]>=0)and(f[j]+v[i]>=f[j+w[i]]) then
begin
f[j+w[i]]:=f[j]+v[i]；
b[q[i],j+w[i]]:=true；
end；
end
else
begin
if (f[j]>=0)and(f[j]+v[i]+v[q[i]]>=f[j+w[i]+w[q[i]]])
and(j+w[i]+w[q[i]]<=n)then
begin
f[j+w[i]+w[q[i]]]:=f[j]+v[i]+v[q[i]]；
b[q[i],j+w[i]+w[q[i]]]:=true；
end；
end；
end；
end；
ans:=0；
for i:=1 to n do
if f[i]>ans then ans:=f[i]；
writeln(ans*10)；
end.
应该是没有什么后效性了啊。。。。哪位大牛给看看