Problem Description

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.

Input Format

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 Format

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

8 4
3 8 7 9 9 4 6 8
2 5 9 4 3 8 9 1

32

Hint

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