1945D.md (2331B)
1 Source: https://codeforces.com/problemset/problem/1945/D 2 3 D. Seraphim the Owl 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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. 22 23 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 \lt 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 \lt k \lt i$, Kirill will have to pay $b_k$ coins to the person at position $k$. Kirill can perform this action any number of times. 24 25 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. 26 27 Help Kirill determine the minimum number of coins he will have to spend in order to not wait too long. 28 29 Input 30 31 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. 32 33 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. 34 35 The second line contains $n$ integers $a_1, a_2, \dots, a_n$ separated by spaces ($1 \le a_i \le 10^9$). 36 37 The third line contains $n$ integers $b_1, b_2, \dots, b_n$ separated by spaces ($1 \le b_i \le 10^9$). 38 39 It is guaranteed that the sum of the values of $n$ over all test cases does not exceed $2 \cdot 10^5$. 40 41 Output 42 43 For each test case, output a single integer — the minimum number of coins Kirill needs to spend. 44 45 Example 46 47 Input 48 49 ``` 50 4 51 52 4 2 53 54 7 3 6 9 55 56 4 3 8 5 57 58 6 2 59 60 6 9 7 1 8 3 61 62 5 8 8 1 4 1 63 64 7 7 65 66 7 2 9 2 6 5 9 67 68 9 1 10 7 1 4 9 69 70 2 1 71 72 2 3 73 74 1 1 75 ``` 76 77 Output 78 79 ``` 80 14 81 22 82 9 83 3 84 ```