记录编号	49514	评测结果	AAAAAAAAAAAWAAWWWWAA
题目名称	还是“金明的预算方案”	最终得分	75
用户昵称	luschegde	是否通过	未通过
代码语言	Pascal	运行时间	0.022 s
提交时间	2012-11-08 12:22:03	内存使用	0.23 MiB

var
n,m,ans:longint;
v,p,q1,q2,q:array[0..3300] of longint;
opt:array[0..3300] of longint;
procedure init;
var
i,x:longint;
begin
assign(input,'budgetb.in');
reset(input);
assign(output,'budgetb.out');
rewrite(output);
readln(n,m);
n:=n div 10;
fillchar(q1,sizeof(q1),0);
fillchar(q2,sizeof(q2),0);
for i:=1 to m do
begin
readln(v[i],p[i],q[i]);
v[i]:=v[i] div 10;
q2[q[i]]:=q1[q[i]];
q1[q[i]]:=i;
end;
close(input);
end;
function max(x,y:longint):longint;
begin
if x>y then exit(x);
exit(y);
end;
procedure main;
var
i,j:longint;
begin
fillchar(opt,sizeof(opt),0);
opt[0]:=1;
for j:=1 to m do
for i:=n downto v[j] do
if q[j]=0 then
begin
if (i-v[j]>=0) and (opt[i-v[j]]>0) then
opt[i]:=max(opt[i],opt[i-v[j]]+v[j]*p[j]);
if (i-v[j]-v[q1[j]]>=0) and (opt[i-v[j]-v[q1[j]]]>0) then
opt[i]:=max(opt[i],opt[i-v[j]-v[q1[j]]]+v[j]*p[j]+v[q1[j]]*p[q1[j]]);
if (i-v[j]-v[q2[j]]>=0) and (opt[i-v[j]-v[q2[j]]]>0) then
opt[i]:=max(opt[i],opt[i-v[j]-v[q2[j]]]+v[j]*p[j]+v[q2[j]]*p[q2[j]]);
if (i-v[j]-v[q1[j]]-v[q2[j]]>=0) and (opt[i-v[j]-v[q1[j]]-v[q2[j]]]>0) then
opt[i]:=max(opt[i],opt[i-v[j]-v[q1[j]]-v[q2[j]]]+v[j]*p[j]+v[q1[j]]*p[q1[j]]+v[q2[j]]*p[q2[j]]);
ans:=max(ans,opt[i]);
end;
end;
procedure print;
begin
writeln((ans-1)*10);
close(output);
end;
begin
init;
main;
print;
end.