典型的二位费用背包问题,主要是边界的考虑
#include <iostream>
#include <cstdio>
#include <cstring>
#define mem(a,b) memset(a,b,sizeof(a))
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
const int inf=0x3f3f3f3f;
int f[100+10][1000+10];
int w[100+10],v[100+10];
int main()
{
int t;
cin>>t;
while(t--)
{
int n,m,l;
cin>>n>>m>>l;
int i,j,k;
for(i=1;i<=n;i++) cin>>w[i]>>v[i];
mem(f,-inf);
mem(f[0],0);
for(i=1;i<=n;i++)
{
for(j=m;j>=0;j--)
{
for(k=l;k>=0;k--)
{
if(j>0&&k>=w[i]) f[j][k]=max(f[j][k],f[j-1][k-w[i]]+v[i]);
}
}
}
if(f[m][l]<0) f[m][l]=0;
cout<<f[m][l]<<endl;
}
return 0;
}