zai xia bei (jin min de yu suan fang an)zhe dao ti ge lei dao le pian pian shuo wo zhi de le 20 fen
xi wang ge wei da niu duo duo bang zhu
xia mian shi yuan dai ma
uses math;
var a:array[1..60,1..3]of longint;
b:array[1..60,0..2]of longint;
f:array[0..3200]of longint;
i,j,n,v,p:longint;
begin
readln(v,n);
v:=v div 10;
fillchar(b,sizeof(b),0);
for i:=1 to n do begin
read(a[i,1],a[i,2],a[i,3]);
readln;
a[i,1]:=a[i,1] div 10;
if a[i,3]<>0 then begin
inc(b[a[i,3],0]);
b[a[i,3],b[a[i,3],0]]:=i;
end;
end;
for i:=1 to n do
if a[i,3]=0 then begin
for j:=v downto a[i,1] do
f[j]:=max(f[j],f[j-a[i,1]]+a[i,2]*a[i,1]);
if b[i,1]<>0 then
for j:=v downto a[i,1]+a[b[i,1],1] do
f[j]:=max(f[j],f[j-a[i,1]-a[b[i,1],1]+a[i,2]*a[i,1]+a[b[i,1],1]*a[b[i,1],2]]);
if b[i,2]<>0 then begin
for j:=v downto a[i,1]+a[b[i,2],1] do
f[j]:=max(f[j],f[j-a[i,1]-a[b[i,2],1]]+a[i,1]*a[i,2]+a[b[i,2],1]*a[b[i,2],2]);
for j:=v downto a[i,1]+a[b[i,2],1]+a[b[i,1],1] do
f[j]:=max(f[j],f[j-a[b[i,1],1]-a[b[i,2],1]-a[i,1]]+a[i,1]*a[i,2]+a[b[i,1],1]*a[b[i,1],2]+a[b[i,2],1]*a[b[i,2],2]);
end;
end;
write(10*f[v]);
end.
bai tuo ge wei le