这些家伙排成一队$$$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