记录编号	354122	评测结果	AAAAAAAAAA
题目名称	[NOIP 2006]金明的预算方案	最终得分	100
用户昵称	zeppoe	是否通过	通过
代码语言	Pascal	运行时间	0.091 s
提交时间	2016-11-19 21:42:41	内存使用	0.29 MiB

program wz;
var
n,m,i,j,k:longint;
v,p,q,num:array[0..60]of longint;
f:array[0..32000]of longint;
w,mo:array[0..60,0..3]of longint;

begin
assign(input,'budget.in');
assign(output,'budget.out');
reset(input);
rewrite(output);
readln(n,m);

for i:=1 to m do
begin
readln(v[i],p[i],q[i]);
if q[i]=0 then begin w[i,0]:=p[i]*v[i];num[i]:=num[i]+1;mo[i,0]:=v[i];end
else
begin
if num[q[i]]=1 then
begin
w[q[i],1]:=w[q[i],0]+p[i]*v[i];inc(num[q[i]]);mo[q[i],1]:=mo[q[i],0]+v[i];
end
else
if num[q[i]]=2 then
begin
w[q[i],2]:=w[q[i],0]+p[i]*v[i];mo[q[i],2]:=mo[q[i],0]+v[i];
w[q[i],3]:=w[q[i],1]+p[i]*v[i];mo[q[i],3]:=mo[q[i],1]+v[i];
end;
end;
end;

for i:=1 to m do
begin
for j:=n downto 0 do
begin
for k:=0 to 3 do
if (j>=mo[i,k])and(f[j-mo[i,k]]+w[i,k]>f[j]) then f[j]:=f[j-mo[i,k]]+w[i,k];
end;
end;

writeln(f[n]);
close(input);
close(output);
end.