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

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

输出样例 #1

32