← 返回题目列表

Codeforces · 802/M3

M3. 愚人节问题(难)

中文机器翻译题面 查看原题

HC 计划2 相当牵强:我们距离 HC 仅有 500 000 天多一点 例如,2 3387,因此我们计划在该版本中包含数十万个问题(我们希望编程竞赛将变得更加流行)。土拨鼠需要开始工作,他们可以使用一个好的计划......

输入

与中等版本相同,但限制已更改: 1 ≤ k ≤ n ≤ 500 000.

输出

与中等版本相同。

示例

输入
复制

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

输出
复制

32