CF802O April Fools' Problem (hard)

HC$ ^{2} $ 的计划相当遥远：例如，距离 HC$ ^{2} $ 3387 还有 500,000 多天，因此我们计划在该期拥有二十几万道题目（我们希望编程竞赛会变得极其流行）。土拨鼠们需要开始工作，而且他们需要一个好的计划…… 土拨鼠们需要在两天内为 HC$^2$ 准备 $k$ 道题。每道题准备好后，还需要打印出来。 在第 $i$ 天准备一道题（每天最多一道）的费用为 $a_i$ 瑞士法郎，在第 $i$ 天打印一道题（每天也最多一道）的费用为 $b_i$ 瑞士法郎。当然，题目不能在准备完成之前打印（但同一天完成准备和打印是可以的）。 准备和打印的最低成本是多少？

输入的第一行包含两个以空格分隔的整数 $n$ 和 $k$（$1 \leq k \leq n \leq 500000$）。 第二行包含 $n$ 个以空格分隔的整数 $a_1,\dots,a_n$，表示准备成本。第三行包含 $n$ 个以空格分隔的整数 $b_1,\dots,b_n$，表示打印成本。 保证 $1 \leq a_i,b_i \leq 10^9$。

输出准备和打印 $k$ 个问题的最低成本，即 $a_{i_1}+a_{i_2}+\dots+a_{i_k}+b_{j_1}+b_{j_2}+\dots+b_{j_k}$ 的最小可能总和，其中 $1\leq i_1

在样例中，一个最优解是在第 $1$ 天准备第一个问题，并在第 $1$ 天打印出来；在第 $2$ 天准备第二个问题，并在第 $4$ 天打印出来；在第 $3$ 天准备第三个问题，并在第 $5$ 天打印出来；在第 $6$ 天准备第四个问题，并在第 $8$ 天打印出来。 由 ChatGPT 5 翻译