#P802O. April Fools' Problem (hard)

    ID: 3876 Type: RemoteJudge 10000ms 256MiB Tried: 0 Accepted: 0 Difficulty: (None) Uploaded By: Tags>binary searchdata structuresflows*2900

April Fools' Problem (hard)

No submission language available for this problem.

Description

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...

Same as the medium version, but the limits have changed: 1 ≤ k ≤ n ≤ 500 000.

Same as the medium version.

Input

Same as the medium version, but the limits have changed: 1 ≤ k ≤ n ≤ 500 000.

Output

Same as the medium version.

Samples

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

32