April Fools' Problem (hard)

题面翻译

$n$ 道题, 第 $i$ 天可以花费 $a_i$ 准备一道题, 花费 $b_i$ 打印一道题, 每天最多准备一道, 最多打印一道, 准备的题可以留到以后打印, 求最少花费使得准备并打印 $k$ 道题。

题目描述

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

输入格式

Same as the medium version, but the limits have changed: $1<=k<=n<=500000$ .

输出格式

Same as the medium version.

样例 #1

样例输入 #1

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

样例输出 #1

32