题目描述

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

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

• 第 $1$ 个任务始终可以完成；
• 当且仅当所有编号小于 $i$ 的任务都至少完成过一次时，第 $i$ 个任务才可以完成。

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

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

• 第一次完成第 $i$ 个任务时，他会获得 $a_i$ 点经验值；
• 之后每次再次完成第 $i$ 个任务时，他会获得 $b_i$ 点经验值。

Monocarp 非常忙碌，所以他最多只能完成 $k$ 次任务。你的任务是计算，在最多完成 $k$ 次任务的情况下，Monocarp 能获得的最大总经验值。

输入格式

第一行包含一个整数 $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$），分别表示任务数量和最多可完成的任务次数。

第二行包含 $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$。

输出格式

对于每个测试用例，输出一个整数，表示在最多完成 $k$ 次任务的情况下，Monocarp 能获得的最大总经验值。

说明/提示

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

由 ChatGPT 4.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

13
4
15
15