72 lines
910 B
ObjectPascal
72 lines
910 B
ObjectPascal
var
|
|
n,m:longint;
|
|
newv,newp:array[-1000..maxint] of longint;
|
|
v,p,q:array[-1000..maxint] of longint;
|
|
f:array[-1000..maxint] of longint;
|
|
|
|
function calc(k:longint):longint;
|
|
var
|
|
i,j,x:longint;
|
|
begin
|
|
x:=1;
|
|
newv[1]:=v[k];
|
|
newp[1]:=p[k];
|
|
for i:=1 to m do
|
|
if q[i]=k then
|
|
begin
|
|
for j:=1 to x do
|
|
begin
|
|
newv[j+x]:=newv[j]+v[i];
|
|
newp[j+x]:=newp[j]+p[i];
|
|
end;
|
|
x:=x*2;
|
|
end;
|
|
exit(x);
|
|
end;
|
|
|
|
procedure dp;
|
|
var
|
|
i,j,k,temp:longint;
|
|
begin
|
|
fillchar(f,sizeof(f),0);
|
|
for i:=1 to m do
|
|
begin
|
|
if q[i]<>0 then continue;
|
|
for j:=n downto 1 do
|
|
for k:=1 to calc(i) do
|
|
if j>=newv[k] then
|
|
if (f[j]<f[j-newv[k]]+newp[k]) then f[j]:=f[j-newv[k]]+newp[k];
|
|
end;
|
|
end;
|
|
|
|
|
|
procedure init;
|
|
var
|
|
i:longint;
|
|
begin
|
|
read(n,m);
|
|
for i:=1 to m do
|
|
begin
|
|
read(v[i],p[i],q[i]);
|
|
p[i]:=p[i]*v[i];
|
|
end;
|
|
end;
|
|
|
|
begin
|
|
assign(input,'budget.in');
|
|
reset(input);
|
|
assign(output,'budget.out');
|
|
rewrite(output);
|
|
|
|
init;
|
|
dp;
|
|
writeln(f[n]);
|
|
|
|
close(input);
|
|
close(output);
|
|
end.
|
|
|
|
|
|
|
|
|