Monocarp 正在玩电脑游戏。为了提升角色等级,他可以完成任务。游戏中有$$$n$$$个任务,编号从$$$1$$$到$$$n$$$。
Monocarp可以按照以下规则完成任务:
- $$$1$$$-st 任务始终可以完成;
- 如果所有任务 $$$j < i$$$ 至少完成一次,则第 $$$i$$$ 任务可以完成。
请注意,Monocarp 可以多次完成同一任务。
每次完成,角色都会获得一定数量的经验值:
- 第一次完成第 $$$i$$$ 个任务时,他获得 $$$a_i$$$ 经验值;
- 随后每次完成第 $$$i$$$ 个任务,他都会获得 $$$b_i$$$ 经验值。
Monocarp 是一个非常忙碌的人,所以他有空闲时间来完成不超过 $$$k$$$ 的任务。你的任务是计算 Monocarp 在完成不超过 $$$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$$$。
输出
对于每个测试用例,打印一个整数 - Monocarp 在完成不超过 $$$k$$$ 任务时可以获得的最大可能总经验。
示例
输入 #1
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
13 4 15 15
注意
在第一个测试用例中,可能的任务完成顺序之一如下:$$$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$$$。