1 /*
 2 Author:    Leo.W
 3 Descriptipn:    在限定購(gòu)買量M，觀看時(shí)間L的情況下，在提供的N件電影中挑選出價(jià)值最大的。
 4 How to Do:    二維費(fèi)用背包問題。dp[j][k]=max{dp[j][k],dp[j-c[i]][k-1]+w[i]};
 5   */
 6 #include <iostream>
 7 #include <string.h>
 8 #include <algorithm>
 9 using namespace std;
10 //#define max(a,b) (a)>(b)?(a):(b)
11 int c[101],w[101];
12 int dp[101][1001];
13 int main(){
14     //freopen("in.txt","r",stdin);
15     int t;
16     scanf("%d",&t);
17     while (t--){
18         int n,m,l;
19         scanf("%d%d%d",&n,&m,&l);
20         int i,j,k;
21         for (i=0;i<n;i++)    scanf("%d%d",&c[i],&w[i]);
22         memset(dp,-1,sizeof(dp));//因?yàn)橛幸痪S要裝滿，即初始化時(shí)不能為零
23         dp[0][0]=0;
24         for (i=0;i<n;i++){
25             for (k=m;k>0;k--){
26                 for (j=l;j>=c[i];j--){//需要判斷是不是從零累積的到
27                     if(dp[k-1][j-c[i]]!=-1&&dp[k][j]<dp[k-1][j-c[i]]+w[i])
28                         dp[k][j]=dp[k-1][j-c[i]]+w[i];
29                 }
30             }
31         }
32         int ms=0;//此處初始很重要 考慮特殊情況為零值
33         for(i=l;i>=0;i--)
34             if(dp[m][i]>ms)
35                 ms=dp[m][i];
36         printf("%d\n",ms);
37     }
38     return 0;
39 }
40