美利坚共产党 @ 2016-02-16 14:27:40
var
n,m,a,b,c,i,j,v0,v1,v2,p0,p1,p2:longint;
v,p,f:array[0..100,0..100] of longint;
begin
readln(n,m);
n:=n div 10;
for i:=1 to m do begin
readln(a,b,c);
if c=0 then c:=i;
for j:=0 to 2 do if v[c,j]=0 then begin
v[c,j]:=a div 10;
p[c,j]:=v[c,j]*b;
break;
end;
end;
for i:=1 to m do if v[i,0]<>0 then begin
v0:=v[i,0];v1:=v[i,1];v2:=v[i,2];
p0:=p[i,0];p1:=p[i,1];p2:=p[i,2];
for j:=n downto 0 do begin
f[i,j]:=f[i-1,j];
if (j>=v0)and(f[i,j]<f[i-1,j-v0]+p0) then f[i,j]:=f[i-1,j-v0]+p0;
if (j>=v0+v1)and(f[i,j]<f[i-1,j-v0-v1]+p0+p1) then f[i,j]:=f[i-1,j-v0-v1]+p0+p1;
if (j>=v0+v2)and(f[i,j]<f[i-1,j-v0-v2]+p0+p2) then f[i,j]:=f[i-1,j-v0-v2]+p0+p2;
if (j>=v0+v1+v2)and(f[i,j]<f[i-1,j-v0-v1-v2]+p0+p1+p2) then f[i,j]:=f[i-1,j-v0-v1-v2]+p0+p1+p2;
end;
end;
write(f[m,n]*10);
end.