fcba @ 2015-10-29 21:52:47
//70分过不了
//原谅我没有缩进和一大堆的debug注释。
program Project1;
var count,n,xh1,xh2,x,pp,y,i,lim,z:longint;
rline,head,used:array[-1..100]of shortint;
line:array[-1..100]of record pre,data:longint;end;
a:array[-1..80]of record price,v,pre:longint;end;
ans:array[0..61,0..32000]of longint;
previous:array[1..61]of longint;
flag:boolean;
function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;
procedure build(x,y:longint);
begin
inc(count);
line[count].pre:=head[x];
line[count].data:=y; //writeln(y);
head[x]:=count; // writeln(x,' ',head[x]);
//writeln ('#');
end;
procedure topo;
var count,xh1,i,s:longint;
begin
count:=0; s:=0;
for xh1:=1 to n do
begin
//writeln(head[xh1]);
//if xh1=4 then writeln('@[url=/space/show?uid=]#$');[/url]
if a[xh1].pre=0 then
begin
previous[xh1]:=s;
//if s=0 then begin if count>1 then previous[xh1]:=rline[count-1] else previous[xh1]:=pp;{ writeln(rline[count-1]); } end;
s:=xh1;
i:=head[xh1]; //writeln(i);
while i<>0 do
begin
inc(count); // writeln(count,' ',line[i].data); halt;
rline[count]:=line[i].data; used[rline[count]]:=1;//writeln(rline[count]);
i:=line[i].pre;
end;
end;
if a[xh1].pre=0 then begin inc(count);
rline[count]:=xh1;end;
end;
end;
begin
assign(input,'lx.in');
assign(output,'lx.out');
reset(input);
rewrite(output);
readln(lim,n);lim:=lim div 10;
flag:=true;
for xh1:=1 to n do
begin
readln(x,y,z);
a[xh1].price:=x div 10;a[xh1].v:=x*y div 10;a[xh1].pre:=z;
if z<>0 then
begin
build(z,xh1);
if (z=1)and flag then begin pp:=xh1; flag:=false;end;
end;
end; // ans[xh1,xh2]:=max(ans[xh1-1,xh2],ans[xh1-1,xh2-a[xh1].price]+a[xh1].v);
topo;
//for xh2:=0 to lim do if a[rline[1]].price<=xh2 then begin ans[rline[1],xh2]:=a[rline[1]].v;end;
for xh1:=1 to n do
for xh2:=1 to lim do
begin
i:=rline[xh1];
if a[i].pre<>0 then
begin
if xh2>=a[i].price then ans[i,xh2]:=max(ans[rline[xh1-1],xh2],ans[rline[xh1-1],xh2-a[i].price]+a[i].v)
else ans[i,xh2]:=ans[rline[xh1-1],xh2];
end
else
begin
if xh2>=a[i].price then ans[i,xh2]:=max(ans[previous[i],xh2],ans[rline[xh1-1],xh2-a[i].price]+a[i].v)
else ans[i,xh2]:=ans[previous[i],xh2];
end;
end;
//writeln(previous[1],' ',ans[previous[1],xh2-a[1].price]+a[1].v);
//writeln(max(ans[2,690],ans[3,660]+a[2].v));
//for xh1:=1 to n do writeln(rline[xh1]);
//for xh1:=1 to n do writeln(previous[xh1]);
//for xh1:=1 to n do writeln(rline[xh1],' ',ans[rline[xh1],a[rline[xh1]].price]);
//for xh1:=1 to n do writeln(previous[xh1]);
writeln(ans[n,lim]*10);
//write(rline[xh1],' ');
//writeln;
end.