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