1 /*
 2 Author:    Leo.W
 3 Descriptipn:    計(jì)算在得到背包最大價(jià)值的同時(shí)，可能得到的其他值，按嚴(yán)格遞減次序，不允許有重復(fù)。    
 4 How to Do:    關(guān)鍵是抽出新序列進(jìn)行排序，更新f[j][k]的信息；
 5   */
 6 #include <iostream>
 7 #include <string.h>
 8 #include <algorithm>
 9 using namespace std;
10 int f[1005][35],temp[65];
11 int w[105],c[105];
12 int main(){
13     int t;
14     //freopen("in.txt","r",stdin);
15     scanf("%d",&t);
16     while(t--){
17         int n,vol,K;
18         scanf("%d%d%d",&n,&vol,&K);
19         int i,j,k;
20         for(i=0;i<n;i++)    scanf("%d",&w[i]);//價(jià)值
21         for(i=0;i<n;i++)    scanf("%d",&c[i]);//體積
22         memset(f,0,sizeof(f));
23         for(i=0;i<n;i++){
24             for(j=vol;j>=c[i];j--){
25                 int cns=0;
26                 for(k=0;k<K;k++){
27                     temp[cns++]=f[j][k];
28                     temp[cns++]=f[j-c[i]][k]+w[i];
29                 }
30                 sort(temp,temp+cns);
31                 int p=0;
32                 for(k=cns-1;k>=0;k--){
33                     if(p>=K)    break;
34                     if(k==cns-1||temp[k]!=temp[k+1])
35                         f[j][p++]=temp[k];
36                 }
37             }
38         }
39         printf("%d\n",f[vol][K-1]);
40     }
41     return 0;
42 }
43