← 返回题目列表

Codeforces · 1945/D

D. 猫头鹰六翼天使

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

这些家伙排成一队$$$n$$$人,从人数$$$i = 1$$$开始,向猫头鹰Serafim询问生命的意义。不幸的是,基里尔正忙着为这个问题编写图例,所以他来得晚了一点,站在队伍的最后,排在第$$$n$$$个人之后。基里尔对这种情况完全不满意,所以他决定贿赂一些走在他前面的人。

对于队列中的第 $$$i$$$ 人,Kirill 知道两个值:$$$a_i$$$ 和 $$$b_i$$$。如果此刻基里尔站在位置$$$i$$$,那么他可以选择任何位置$$$j$$$,使得$$$j < i$$$并与位置$$$j$$$的人交换位置。在这种情况下,基里尔将不得不向他支付 $$$a_j$$$ 硬币。对于每个$$$k$$$,使得$$$j < k < i$$$,基里尔将不得不向位置$$$k$$$的人支付$$$b_k$$$硬币。基里尔可以多次执行此操作。

基里尔很节俭,所以他想花尽可能少的硬币,但他不想等待太久,所以基里尔相信他应该是最先排队的$$$m$$$人之一。

帮助基里尔确定他必须花费的最少金币数量,以免等待太久。

输入

每个测试由多组输入数据组成。第一行包含一个整数 $$$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 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数——基里尔需要花费的最小硬币数量。

示例

输入 #1

4
4 2
7 3 6 9
4 3 8 5
6 2
6 9 7 1 8 3
5 8 8 1 4 1
7 7
7 2 9 2 6 5 9
9 1 10 7 1 4 9
2 1
2 3
1 1

输出 #1

14
22
9
3