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.

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

32