← 返回题目列表

Codeforces · 1633/D

D. 让他们平等

中文机器翻译题面 查看原题

您有一个大小为 $$$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