CF1945D Seraphim the Owl

有 $n$ 个人排成一队，从第 $i=1$ 号人开始，依次向猫头鹰 Serafim 询问人生的意义。不幸的是，Kirill 因为忙于为本题编写题面，来晚了，他只能站在第 $n$ 个人之后的队尾。Kirill 对此非常不满，于是决定贿赂他前面的一些人。 对于队列中的第 $i$ 个人，Kirill 知道两个数值：$a_i$ 和 $b_i$。如果此时 Kirill 站在第 $i$ 个位置，他可以选择任意一个 $j$，其中 $j < i$，并与第 $j$ 个位置的人交换位置。此时，Kirill 需要向第 $j$ 个人支付 $a_j$ 枚硬币。同时，对于每一个 $k$，满足 $j < k < i$，Kirill 还需要向第 $k$ 个人分别支付 $b_k$ 枚硬币。Kirill 可以进行任意多次这样的操作。 Kirill 很节俭，他希望花费尽量少的硬币，但又不想等太久，因此他希望自己最终能排在队伍的前 $m$ 个位置之中。 请你帮助 Kirill 计算，为了不等待太久，他至少需要花费多少硬币。

每组测试数据包含多组输入。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的组数。接下来是每组测试用例的描述。 每组测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le m \le n \le 200\,000$），分别表示除了 Kirill 以外队伍中的人数，以及 Kirill 最多能接受的最终排队位置。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，用空格隔开（$1 \le a_i \le 10^9$）。 第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$，用空格隔开（$1 \le b_i \le 10^9$）。 保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

对于每组测试用例，输出一个整数，表示 Kirill 至少需要花费的硬币数。

由 ChatGPT 4.1 翻译