题目描述

给出 $n$ 件物品的价值和体积，问在总体积不超过 $v$ 时的第 $k$ 大价值（去重后）。

比如样例，价值为 $9$ 时总共有 $3$ 种：$4+5$，$2+3+4$，$1+3+5$，但它们只算一种。

输入格式

第一行为用例组数 $T$，每组用例第一行为三个整数 $n,v$ 和 $k$；

第二行 $n$ 个整数表示这 $n$ 件物品的价值，第三行 $n$ 个整数表示这 $n$ 件物品的体积。

$N \le 100, V \le 1000, K \le 30, T \le 10，价值 \le 1000, 体积 \le 1000$ 。

输出格式

对于每组用例，输出总体积不超过 $v$ 的第 $k$ 大价值。

样例

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