让他们平等

有一个大小为 的整数数组 。最初，数组的所有元素都等于 。您可以执行以下操作：选择两个整数 ( ) 和 ( )( )，然后将 的值增加 （即变为 ）。

完成所有运算后，所有 和 都将得到 个硬币。

你的任务是确定进行不超过 次运算所能得到的硬币的最大数量。

输入

第一行包含一个整数 ( ) - 测试用例的数量。

每个测试用例的第一行包含两个整数 和 ( ) - 分别是数组的大小和最大操作次数。

第二行包含 个整数 ( )。

第三行包含 个整数 （ ）。( ).

所有测试用例的 之和不超过 。

输出

对于每个测试用例，打印一个整数 - 通过不超过 的操作可以获得的最大硬币数。

样例

输入

4
4 4
1 7 5 2
2 6 5 2
3 0
3 5 2
5 4 7
5 9
5 2 5 6 3
5 9 1 9 7
6 14
11 4 6 2 8 16
43 45 9 41 15 38

输出

9
0
30
167