您有一个大小为 $$$n$$$ 的整数数组 $$$a$$$。最初,数组的所有元素都等于 $$$1$$$。您可以执行以下操作:选择两个整数 $$$i$$$ ($$$1 \le i \le n$$$) 和 $$$x$$$ ($$$x > 0$$$),然后将 $$$a_i$$$ 的值增加 $$$\left\lfloor\frac{a_i}{x}\right\rfloor$$$ (即使 $$$a_i = a_i + \left\lfloor\frac{a_i}{x}\right\rfloor$$$)。
执行完所有操作后,您将收到所有 $$$i$$$ 且 $$$a_i = b_i$$$ 的 $$$c_i$$$ 硬币。
你的任务是确定通过执行不超过 $$$k$$$ 操作可以获得的最大硬币数量。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 10^3; 0 \le k \le 10^6$$$) - 分别是数组的大小和最大操作数。
第二行包含 $$$n$$$ 整数 $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 10^3$$$)。
第三行包含 $$$n$$$ 整数 $$$c_1, c_2, \dots, c_n$$$ ($$$1 \le c_i \le 10^6$$$)。
所有测试用例的 $$$n$$$ 总和不超过 $$$10^3$$$。
输出
对于每个测试用例,打印一个整数 - 通过执行不超过 $$$k$$$ 操作可以获得的最大硬币数量。
示例
输入 #1
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
输出 #1
9 0 30 167