Pressing and Glittering Records

Time limit3sMemory limit128 MB

Summary

Pick k pressing days and k glittering days over n days so each press day precedes its glitter day at minimum total cost.

Level: Medium7 of 10
Topics: Greedy, Heap
Solved: No attempts yet

Problem

A rapper is producing a special vinyl edition of his album. Every record must first be pressed at a pressing plant, and only then coated with glitter at a glitter shop before it is finished.

The rapper has a contract to make exactly $k$ records. The pressing plant and the glitter shop can each handle only one record per day. Every record must be pressed before it is glittered, but the same record may be both pressed and glittered on a single day. A record that has been pressed but not yet glittered can be stored for as long as needed at no extra cost.

For each of the next $n$ days you are given that day's pressing cost and glittering cost. Decide on which days to press and on which days to glitter so that all $k$ records are finished at the minimum possible total cost.

Input

The first line contains two integers $n$ and $k$ ( $1 \le k \le n \le 5 \times 10^5$ ).

The second line contains $n$ positive integers, each at most $10^9$ ; the $i$ -th value is the pressing cost on day $i$ .

The third line contains $n$ positive integers, each at most $10^9$ ; the $i$ -th value is the glittering cost on day $i$ .

Output

Print a single integer: the minimum total cost to produce $k$ glitter-coated records.

Hint

For the sample input, one optimal plan is: press and glitter the first record on day 1; press the second record on day 2 and glitter it on day 4; press the third record on day 3 and glitter it on day 5; press the fourth record on day 6 and glitter it on day 8. The total cost is 32.

Examples2

Example 1
Input
```
8 4
3 8 7 9 9 4 6 8
2 5 9 4 3 8 9 1
```
Expected output
```
32
```
Example 2
Input
```
1 1
5
7
```
Expected output
```
12
```