← 返回题目列表

Codeforces · 1914/C

C. 任务

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

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$$$。