roy12 2008-08-01 06:56:00
点我顶贴
收藏
删除
var a,v:array[1..1000]of longint;
f:array[0..10000,0..1000]of longint;
i,j,k,t,m,n,ans:longint;
begin
readln(n,m,t);
for i:=1 to n do
readln(a[i],v[i]);
for i:=1 to n do
for j:=1 to m do
f[i,m]:=-1;
f[0,0]:=0;
for i:=1 to n do
for j:=t-a[i] downto 0 do
for k:=m-1 downto 0 do
if (f[j,k]>=0)and(j+a[i]<=t)and(k+1<=m)
and(f[j,k]+v[i]>f[j+a[i],k+1]) then
f[j+a[i],k+1]:=f[j,k]+v[i];
ans:=0;
for i:=1 to t do
if f[i,m]>ans then ans:=f[i,m];
writeln(ans);
end.