Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

O. April Fools' Problem (hard)

time limit per test

10 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThe plans for HC^{2} are rather far-fetched: we are just over 500 000 days away from HC^{2} 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 ≤ *k* ≤ *n* ≤ 500 000.

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

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/13/2018 19:57:08 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|