P4694 [PA 2013] Raper

You need to produce $k$ optical discs. Each disc must go through two steps: first it is pressed at factory A, and then it is sent to factory B to be coated with a reflective layer. You know the daily cost for factories A and B to process one disc. You have $n$ days. Each day, you may first send one disc to factory A for processing (or send none), and then send one disc that has already been processed at factory A to factory B for processing (or send none). Each factory can process at most one disc per day. It is allowed for the same disc to be fully produced within a single day. We assume there is no cost to store unprocessed or half-finished discs. Find the minimum total cost to produce $k$ discs.

The first line contains two integers $n, k$, meaning there are $n$ days and you need to produce $k$ optical discs. The second line contains $n$ integers. The $i$-th integer is the cost of sending a disc to factory A on day $i$. The third line contains $n$ integers. The $i$-th integer is the cost of sending a disc to factory B on day $i$.

Output one integer on a single line, the minimum total cost.

It is guaranteed that $1 \leqslant k \leqslant n \leqslant 5 \times 10^5,$ and $1 \leqslant a_i, b_i \leqslant 10^9$. Note: 3 sets of hack testdata were added. If you do not pass them, 3 points will be deducted. Translated by ChatGPT 5