budiebuai 2008-07-13 06:09:00
点我顶贴
收藏
删除
program dddd；
type
wer=record
r,e,w:longint；
y,u:array[1..100]of longint；
end；
var
n,m,a,b,c,i,t,j,ty,k:longint；
f:array[1..100]of wer；
v:array[0..32000]of longint；
begin
read(n,m)；
t:=0；
for i:= 1 to m do
begin
read(a,b,c)；
if c=0 then
begin
inc(t)；
f[t].r:=a；
f[t].e:=b；
end；
if c<>0 then
begin
inc(f[c].w)；
f[c].y[f[c].w]:=a；
f[c].u[f[c].w]:=b；
end；
end；
for i:=1 to t do
for j:=n downto 1 do
begin
if j>=f[i].r then
begin
ty:=v[j-f[i].r]+f[i].r*f[i].e；
if ty>v[j] then
v[j]:=ty；
for k:= 1 to f[i].w do
if j-f[i].r-f[i].y[k]>=0 then
begin
ty:=v[j-f[i].r-f[i].y[k]]+f[i].y[k]*f[i].u[k]+f[i].e*f[i].r；
if ty>v[j] then
v[j]:=ty；
end；
end；
end；
write(v[n])；
end.