Description

今天阳光正好，WWN学姐想去超市买几包零食送给正在敲代码的小萌新。

超市里的商品琳琅满目，大大小小价格不一的商品让热爱思考的学姐想到了一个有趣的问题:

他手上的袋子可以装下体积为V的零食，而每件商品都有自己所对应的价格和体积，那么她这次购物最大花销会是多少呢？

但是聪明的学姐很快就想出了答案，这让她感觉很没有挑战性...于是学姐又继续思考:

那么我这次购物第K大花销会是多少呢？

这次可让学姐把自己给难住了

那么就请你设计一个算法帮助学姐解决这个问题吧

Input Format

第一行包含一个整数T，代表测试数据组数

对接下来的T组数据，每组数据有三行

第一行有三个整数N,V,K(N <= 100 , V <= 1000 , K <= 30),分别代表零食数量、学姐手上袋子的体积和所要求的第K大花销

第二行有N个整数，分别代表每件零食的价格

第三行有N个整数，分别代表每件零食的体积

Output Format

T行整数，分别是每组数据的解（解的大小将小于2^31）

3
5 10 2
1 2 3 4 5
5 4 3 2 1
5 10 12
1 2 3 4 5
5 4 3 2 1
5 10 16
1 2 3 4 5
5 4 3 2 1​

12
2
0​

Hint

可以参考背包九讲里面的思路，改自HDUOJ2639## Source

动态规划