311179: CF1945D. Seraphim the Owl
Description
The guys lined up in a queue of $n$ people, starting with person number $i = 1$, to ask Serafim the Owl about the meaning of life. Unfortunately, Kirill was very busy writing the legend for this problem, so he arrived a little later and stood at the end of the line after the $n$-th person. Kirill is completely dissatisfied with this situation, so he decided to bribe some people ahead of him.
For the $i$-th person in the queue, Kirill knows two values: $a_i$ and $b_i$. If at the moment Kirill is standing at position $i$, then he can choose any position $j$ such that $j < i$ and exchange places with the person at position $j$. In this case, Kirill will have to pay him $a_j$ coins. And for each $k$ such that $j < k < i$, Kirill will have to pay $b_k$ coins to the person at position $k$. Kirill can perform this action any number of times.
Kirill is thrifty, so he wants to spend as few coins as possible, but he doesn't want to wait too long, so Kirill believes he should be among the first $m$ people in line.
Help Kirill determine the minimum number of coins he will have to spend in order to not wait too long.
InputEach test consists of several sets of input data. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then follows the description of the test case.
The first line of each test case contains two integers $n$ and $m$ ($1 \le m \le n \le 200\,000$) — the number of people in the queue besides Kirill and the maximum allowable final position of Kirill, respectively.
The second line contains $n$ integers $a_1, a_2, \dots, a_n$ separated by spaces ($1 \le a_i \le 10^9$).
The third line contains $n$ integers $b_1, b_2, \dots, b_n$ separated by spaces ($1 \le b_i \le 10^9$).
It is guaranteed that the sum of the values of $n$ over all test cases does not exceed $2 \cdot 10^5$.
OutputFor each test case, output a single integer — the minimum number of coins Kirill needs to spend.
ExampleInput4 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 1Output
14 22 9 3
Output
有n个人排成一行，从第i=1个人开始，向Serafim the Owl询问生活的意义。Kirill来晚了，站在第n个人后面。Kirill知道对于队列中的第i个人，有两个值：a_i和b_i。如果Kirill目前站在位置i，他可以选择任意一个位置j（j
输入输出数据格式：
输入：
- 第一行包含一个整数t（1≤t≤10^4），表示测试用例的数量。
- 每个测试用例的第一行包含两个整数n和m（1≤m≤n≤200,000），分别表示队列中除Kirill外的人数和Kirill允许的最大最终位置。
- 每个测试用例的第二行包含n个整数a_1, a_2, ..., a_n（1≤a_i≤10^9），由空格分隔。
- 每个测试用例的第三行包含n个整数b_1, b_2, ..., b_n（1≤b_i≤10^9），由空格分隔。
- 保证所有测试用例的n值之和不超过2×10^5。
输出：
- 对于每个测试用例，输出一个整数，表示Kirill需要花费的最少硬币数。
示例：
输入：
```
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
```
输出：
```
14
22
9
3
```题目大意： 有n个人排成一行，从第i=1个人开始，向Serafim the Owl询问生活的意义。Kirill来晚了，站在第n个人后面。Kirill知道对于队列中的第i个人，有两个值：a_i和b_i。如果Kirill目前站在位置i，他可以选择任意一个位置j（j