Problem1424--April Fools' Problem (hard)

1424: April Fools' Problem (hard)

Time Limit: 2 Sec  Memory Limit: 256 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

time limit per test
10 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The plans for HC2 are rather far-fetched: we are just over 500 000 days away from HC2 3387, for example, and accordingly we are planning to have a couple hundred thousand problems in that edition (we hope that programming contests will become wildly more popular). The marmots need to get to work, and they could use a good plan...

Input

Same as the medium version, but the limits have changed: 1≤kn≤500000.

Output

Same as the medium version.

Example
Input
8 4
3 8 7 9 9 4 6 8
2 5 9 4 3 8 9 1
Output
32

Source/Category