310960: CF1914C. Quests

C. Queststime limit per test2.5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Monocarp is playing a computer game. In order to level up his character, he can complete quests. There are $n$ quests in the game, numbered from $1$ to $n$.

Monocarp can complete quests according to the following rules:

• the $1$-st quest is always available for completion;
• the $i$-th quest is available for completion if all quests $j < i$ have been completed at least once.

Note that Monocarp can complete the same quest multiple times.

For each completion, the character gets some amount of experience points:

• for the first completion of the $i$-th quest, he gets $a_i$ experience points;
• for each subsequent completion of the $i$-th quest, he gets $b_i$ experience points.

Monocarp is a very busy person, so he has free time to complete no more than $k$ quests. Your task is to calculate the maximum possible total experience Monocarp can get if he can complete no more than $k$ quests.

Input

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5$; $1 \le k \le 2 \cdot 10^5$) — the number of quests and the maximum number of quests Monocarp can complete, respectively.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^3$).

The third line contains $n$ integers $b_1, b_2, \dots, b_n$ ($1 \le b_i \le 10^3$).

Additional constraint on the input: the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, print a single integer — the maximum possible total experience Monocarp can get if he can complete no more than $k$ quests.

ExampleInput

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

Output

13
4
15
15

Note

In the first test case, one of the possible quest completion sequences is as follows: $1, 1, 2, 3, 2, 4, 4$; its total experience is equal to $\underline{4} + 1 + \underline{3} + \underline{1} + 1 + \underline{2} + 1 = 13$ (the underlined numbers correspond to the instances when we complete a quest for the first time).

In the second test case, one of the possible quest completion sequences is as follows: $1, 1$; its total experience is equal to $\underline{1} + 3 = 4$.

In the third test case, one of the possible quest completion sequences is as follows: $1, 2, 2, 2, 3$; its total experience is equal to $\underline{3} + \underline{2} + 3 + 3 + \underline{4} = 15$.

题目大意：
Monocarp 在玩一个电脑游戏，为了提升角色等级，他可以完成一些任务。游戏中有 n 个任务，编号从 1 到 n。Monocarp 可以根据以下规则完成任务：第一个任务始终可以完成；第 i 个任务可以在完成所有编号小于 i 的任务至少一次后完成。Monocarp 可以多次完成同一个任务。对于每次完成，角色会获得一些经验值：第一次完成第 i 个任务时，他会获得 a_i 经验值；之后每次完成第 i 个任务，他会获得 b_i 经验值。Monocarp 非常忙碌，因此他最多有 k 次时间去完成任务。任务是计算 Monocarp 如果最多完成 k 次任务，可以获得的最大总经验值。

输入输出数据格式：
输入：
- 第一行包含一个整数 t（1 ≤ t ≤ 10^4），表示测试用例的数量。
- 每个测试用例的第一行包含两个整数 n 和 k（1 ≤ n ≤ 2 × 10^5；1 ≤ k ≤ 2 × 10^5），分别表示任务的数量和 Monocarp 可以完成的任务的最大次数。
- 第二行包含 n 个整数 a_1, a_2, …, a_n（1 ≤ a_i ≤ 10^3）。
- 第三行包含 n 个整数 b_1, b_2, …, b_n（1 ≤ b_i ≤ 10^3）。
- 输入数据的附加限制：所有测试用例的 n 之和不超过 2 × 10^5。

输出：
- 对于每个测试用例，输出一个整数，表示 Monocarp 如果最多完成 k 次任务，可以获得的最大总经验值。题目大意： Monocarp 在玩一个电脑游戏，为了提升角色等级，他可以完成一些任务。游戏中有 n 个任务，编号从 1 到 n。Monocarp 可以根据以下规则完成任务：第一个任务始终可以完成；第 i 个任务可以在完成所有编号小于 i 的任务至少一次后完成。Monocarp 可以多次完成同一个任务。对于每次完成，角色会获得一些经验值：第一次完成第 i 个任务时，他会获得 a_i 经验值；之后每次完成第 i 个任务，他会获得 b_i 经验值。Monocarp 非常忙碌，因此他最多有 k 次时间去完成任务。任务是计算 Monocarp 如果最多完成 k 次任务，可以获得的最大总经验值。 输入输出数据格式： 输入： - 第一行包含一个整数 t（1 ≤ t ≤ 10^4），表示测试用例的数量。 - 每个测试用例的第一行包含两个整数 n 和 k（1 ≤ n ≤ 2 × 10^5；1 ≤ k ≤ 2 × 10^5），分别表示任务的数量和 Monocarp 可以完成的任务的最大次数。 - 第二行包含 n 个整数 a_1, a_2, …, a_n（1 ≤ a_i ≤ 10^3）。 - 第三行包含 n 个整数 b_1, b_2, …, b_n（1 ≤ b_i ≤ 10^3）。 - 输入数据的附加限制：所有测试用例的 n 之和不超过 2 × 10^5。 输出： - 对于每个测试用例，输出一个整数，表示 Monocarp 如果最多完成 k 次任务，可以获得的最大总经验值。