该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

弗拉德正在玩一款名叫迅捷猎人的电脑游戏。为了提升角色等级，他可以完成任务。游戏中有 n 个任务，编号从 1 到 n。

弗拉德 可以按照以下规则完成任务：

• 第 1 个任务总是可以完成的；
• 如果所有任务 j<i 都完成了至少一次，那么第i 个任务就可以完成。

请注意，弗拉德 可以多次完成同一个任务。

每次完成任务，角色都会获得一定数量的经验值：

• 第一次完成第 i个任务，获得 $a_i$ 点经验值；
• 之后每完成一次第i个任务，可以获得 $b_i$ 点经验值。

弗拉德 是个大忙人，所以他有空闲时间完成的任务不超过 k个。你的任务是计算 Nadia 在完成不超过 k个任务的情况下可能获得的最大总经验值。

输入

第一行包含一个整数 t ( $1 \le t \le 10^4$ ) —测试用例的数量。

每个测试用例的第一行包含两个整数 n 和 k ( $1 \le n \le 2 \cdot 10^5$; $1 \le k \le 2 \cdot 10^5$)--分别是任务数和 Monocarp 能完成的最大任务数。

第二行包含 n个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^3$)

第三行包含 n 个整数$b_1, b_2, \dots, b_n$ ($1 \le b_i \le 10^3$).

输入的附加限制条件：所有测试用例的 n 总和不超过 $2 \cdot 10^5$。

输出

对于每个测试用例，打印一个整数—-如果单卡完成的任务不超过 k ，单卡可能获得的最大总经验值。

样例

4
4 7
4 3 1 2
1 1 1 1
3 2
1 2 5
3 1 8
5 5
3 2 4 1 4
2 3 1 4 7
6 4
1 4 5 4 5 10
1 5 1 2 5 1

13
4
15
15

Limitation

1s, 1024KiB for each test case.