题目：

学过01背包都知道有道入门题目叫  Bone Collector（hdu2606）, 给你n个石头，每个石头占背包的v[i] 容量， 价值为w[i]，给你背包的容量， 要你求出所能得到的最大价值， 也就是最优解，这道题的升级版就是要你求第k优解。

思路：我们找到01背包的原理就是通过状态转移方程式来进行继承上一个状态的，那我们所要求的第k优解肯定就在转移方程式中出现过，也就是说， 转移中，所有可能出现的情况的都会出来，那么我们就把转移状态方程式变成两个有序队列， 再对两个队列进行遍历，求出1 - k优解。

有一种情况需要根据题意进行判断就是我们两种不同操作的方案但是结果一样，那么需要算为同一种还是两种。

/*
Algorithm:01背包 + 第k优解
Author: anthony1314
Creat Time:
Time Complexity:
*/

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#include<stack>
#include<cstring>
#include<cstdio>
//#include<bits/stdc++.h>
#define ll long long
#define maxn 1005
#define mod 1e9 + 7
#define line printf("--------------");
using namespace std;
int dp[1005][32];
int v[105], w[105];
int aa[35], bb[35];
int main() {
    int t;
    cin>>t;
    while(t--) {
        int n, vv, k;
        cin>>n>>vv>>k;
        memset(dp, 0, sizeof(dp));
        memset(w, 0, sizeof(w));
        memset(v, 0, sizeof(v));
        memset(aa, 0, sizeof(aa));
        memset(bb, 0, sizeof(bb));
        for(int i = 1; i <= n; i++) {
            scanf("%d", &w[i]);
        }
        for(int i = 1; i <= n; i++) {
            scanf("%d", &v[i]);
        }
        for(int i = 1; i <= n; i++){
            for(int j = vv; j >= v[i]; j--){
                int kk;
                for(kk = 1; kk <= k; kk++){
                    aa[kk] = dp[j - v[i]][kk] + w[i];
                    bb[kk] = dp[j][kk];            
                }
                int a = 1, b = 1, c = 1;
                while(c <= k && (a <= k || b <= k)){
                    if(aa[a] > bb[b]){
                        dp[j][c] = aa[a];
                        a++;
                    }else{
                        dp[j][c] = bb[b];
                        b++;
                    }
                    if(dp[j][c] != dp[j][c - 1]){
                        c++;
                    }
                }
            }
        }
        cout<<dp[vv][k]<<endl;
        
    }


    return 0;
}