CF1914C.Quests

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 \lt 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.

Monocarp 正在玩一款电脑游戏。为了提升角色等级，他可以完成任务。游戏中共有 $n$ 个任务，编号从 $1$ 到 $n$。

Monocarp 可以按照以下规则完成任务：

• 第 $1$ 个任务始终可被完成；
• 第 $i$ 个任务可被完成，当且仅当所有编号 $j < i$ 的任务都至少已被完成过一次。

注意：Monocarp 可以多次完成同一个任务。

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

• 第 $i$ 个任务首次完成时，获得 $a_i$ 点经验值；
• 第 $i$ 个任务后续每次完成时，获得 $b_i$ 点经验值。

Monocarp 非常忙，因此他仅有时间完成至多 $k$ 个任务。你的任务是：计算 Monocarp 在最多完成 $k$ 个任务的前提下，所能获得的最大总经验值。

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

第一行包含一个整数 $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$。

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.

对于每个测试用例，输出一个整数——即 Monocarp 最多完成 $k$ 个任务时所能获得的最大总经验值。

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

在第一个测试用例中，一种可能的任务完成序列为：$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$。