Pku3900 The Robbery

在布加勒斯特市中心的一座银行金库中，有 $N$ 个编号为 $1$ 到 $N$ 的箱子。编号为 $k$ 的箱子中装有 $k$ 颗钻石，每颗钻石的重量为 $W_k$，价值为 $C_k$。

John 和 Brus 想从中带走一些钻石，但他们能够携带的钻石总重量不能超过 $M$。请计算他们能够带走的钻石的最大总价值。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量。

每组测试用例包含三行：

• 第一行包含两个整数 $N$ 和 $M$，分别表示箱子的数量和能够携带的最大总重量；
• 第二行包含 $N$ 个整数 $W_1,W_2,\ldots,W_N$，其中 $W_k$ 表示第 $k$ 个箱子中每颗钻石的重量；
• 第三行包含 $N$ 个整数 $C_1,C_2,\ldots,C_N$，其中 $C_k$ 表示第 $k$ 个箱子中每颗钻石的价值。

输出格式

对于每组测试用例，输出一行一个整数，表示在钻石总重量不超过 $M$ 的条件下能够获得的最大总价值。

样例输入

2
2 4
3 2
5 3
3 100
4 7 1
5 9 2

样例输出

6
29

数据范围

• $1\le T\le 74$；
• $1\le N\le 15$；
• $1\le M\le 10^9$；
• $1\le W_k,C_k\le 10^9$。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

2
2 4
3 2
5 3
3 100
4 7 1
5 9 2

输出

6
29