1816 - April Fools' Problem (hard)

1816.April Fools' Problem (hard)

Time Limit: 1s Memory Limit: 256MB

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 Format(From the terminal/stdin)

Same as the medium version, but the limits have changed: 1 \le k \le n \le 500000.

Output Format(To the terminal/stdout)

Same as the medium version.

Sample Input

Copy

8 4
3 8 7 9 9 4 6 8
2 5 9 4 3 8 9 1
 · \n
 · · · · · · · \n
 · · · · · · · \n

Sample Output

Copy

32
  \n

Submit

请先登录

Submit

题解(0)