Seraphim the Owl
Contest: Codeforces Round 935 (Div. 3)
Difficulty rating: 1300
Tags: dp, greedy

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.

Input format:
Each 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$$$.

Output format:
For each test case, output a single integer — the minimum number of coins Kirill needs to spend.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
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

Example output:
14
22
9
3

Editorial:
Let's consider a greedy approach. Suppose we are standing at position $$$i$$$. Find the first $$$j$$$ such that $$$j < i$$$ and $$$a_j < b_j$$$. If such $$$j$$$ exists and $$$j > m$$$, then swap with $$$j$$$. This will be optimal, because in any case we will have to pay the people at positions $$$i - 1, i - 2, \dots, j$$$ some amount of coins, and in this way we will pay each person at position $$$k$$$ where $$$i > k > j$$$, $$$b_k$$$ coins. According to the greedy condition $$$b_k > a_k$$$, so $$$b_k$$$ is the minimum amount of coins we can pay $$$k$$$-th person. We will also pay the $$$j$$$-th person $$$a_j$$$ coins. $$$a_j < b_j$$$, hence we will pay the minimum amount of coins to all people.
If such $$$j$$$ does not exist, then it is advantageous for us to choose the final position $$$f$$$, such that $$$1 \le f \le m$$$, in order to finish the movements and overpay as little as possible. Simply check each $$$f$$$, recalculating the answer using prefix sums on array $$$b$$$ and choose the smallest one.
Asymptotics: $$$\mathcal{O}(n)$$$.