CF802O April Fools' Problem (hard)

HC $ ^{2} $ 的计划相当遥远：例如，距离 HC $ ^{2} $ 3387 还有 500,000 多天，因此我们计划在该期拥有二十几万道题目（我们希望编程竞赛会变得极其流行）。土拨鼠们需要开始工作，而且他们需要一个好的计划……

与中等版本相同，但是数据范围发生了变化：$1 \leq k \leq n \leq 500000$。 $1 \leq a_i, b_i \leq 10^9$。

与中等版本相同。

由 ChatGPT 5 翻译