题目描述
LHX 正在玩一款电脑游戏。为了提升角色等级，他可以完成任务。游戏中有 $n$ 个任务，编号从 $1$ 到 $n$ 。
LHX 可以按照以下规则完成任务：
- 第 $1$ 个任务总是可以完成的；
- 如果任务 i 之前的所有任务都完成了至少一次，那么第 i 个任务就可以完成。
请注意，LHX 可以多次完成同一个任务。
每次完成任务，角色都会获得一定数量的经验值：
- 第一次完成 i 任务，获得 $a_i$ 点经验值；
- 之后每完成一次 i 任务，可以获得 $b_i$ 点经验值。
LHX 是个大忙人，所以他有空闲时间完成的任务不超过 $k$ 个。你的任务是计算 LHX 在完成不超过 $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$ )--分别是任务数和 LHX 能完成的最大任务数。
第二行包含 $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$ 。
输出
对于每个测试用例，打印一个整数——如果 LHX 完成的任务不超过 $k$ ， LHX 可能获得的最大总经验值。
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
提示
在第一个测试案例中，其中一个可能的任务完成顺序如下： $1, 1, 2, 3, 2, 4, 4$ ；其总经验等于 $\underline{4} + 1 + \underline{3} + \underline{1} + 1 + \underline{2} + 1 = 13$ （下划线数字对应的是我们第一次完成任务的情况）。
在第二个测试案例中，其中一个可能的任务完成序列如下： $1, 1$ ；总经验等于 $\underline{1} + 3 = 4$ 。
在第三个测试案例中，其中一个可能的任务完成顺序如下： $1, 2, 2, 2, 3$ ；总经验等于 $\underline{3} + \underline{2} + 3 + 3 + \underline{4} = 15$ 。