← 返回题目列表

Codeforces · 1996/F

F. 炸弹

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

Sparkle 为您提供两个长度为 $$$n$$$ 的数组 $$$a$$$ 和 $$$b$$$。最初,您的分数是 $$$0$$$。在一次操作中,您可以选择一个整数 $$$i$$$ 并将 $$$a_i$$$ 添加到您的分数中。然后,您必须设置 $$$a_i$$$ = $$$\max(0, a_i - b_i)$$$。

在 Sparkle 引爆核弹之前,你只有时间执行 $$$k$$$ 操作!经过 $$$k$$$ 操作后您可以获得的最高分数是多少?

输入

第一行包含 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。

每个测试用例的第一行包含 $$$n$$$ 和 $$$k$$$ ($$$1 \leq n \leq 2 \cdot 10^5, 1 \leq k \leq 10^9$$$) — 数组的长度和可以执行的操作数。

以下行包含 $$$n$$$ 整数 $$$a_1, a_2, ... a_n$$$ ($$$1 \leq a_i \leq 10^9$$$)。

以下行包含 $$$n$$$ 整数 $$$b_1, b_2, ... b_n$$$ ($$$1 \leq b_i \leq 10^9$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数,即经过$$$k$$$操作后可以获得的最高分数。

示例

输入 #1

5
3 4
5 6 7
2 3 4
5 9
32 52 68 64 14
18 14 53 24 8
5 1000
1 2 3 4 5
5 4 3 2 1
1 1000000
1000000
1
10 6
3 3 5 10 6 8 6 8 7 7
6 1 7 4 1 1 8 9 3 1

输出 #1

21
349
27
500000500000
47