学步园

#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 105
#define maxl 1005
#define INF 0x7fffffff
using namespace std;
int c[maxn],v[maxn];
int f[maxl][maxn];
int max(int x,int y)
{
    return x>y?x:y;
}
int main()
{
    int t,n,m,l;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&n,&m,&l);
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&c[i],&v[i]);
        }
        //memset(f,0,sizeof(f));
        for(int j=0;j<=l;j++)
        for(int k=0;k<=m;k++)
        f[j][k]=-INF;
        f[0][0]=0;

        for(int i=1;i<=n;i++)
        {
            for(int j=l;j>=c[i];j--)//一维限制
            {
                for(int k=m;k>=1;k--)//二维限制
                {
                    f[j][k]=max(f[j][k],f[j-c[i]][k-1]+v[i]);

                }
            }
        }
        int Max=0;
        for(int i=0;i<=l;i++)
        {                           //固定一维，求最大值
            if(Max<f[i][m])         //由于初始化设置为-INF
                                    //所以得在【0，m】里找
                                    //答案
            Max=f[i][m];
        }
        printf("%d\n",Max);
    }
	return 0;
}