P4694 [PA 2013] Raper

你需要生产 $k$ 张光盘。每张光盘都要经过两道工序：先在 A 工厂进行挤压，再送到 B 工厂涂上反光层。 你知道每天 A、B 工厂分别加工一张光盘的花费。你现在有 $n$ 天时间，每天可以先送一张光盘到 A 工厂（或者不送），然后再送一张已经在 A 工厂加工过的光盘到 B 工厂（或者不送），每家工厂一天只能对一张光盘进行操作，同一张光盘在一天内生产出来是允许的。我们假定将未加工的或半成品的光盘保存起来不需要费用。 求生产出 $k$ 张光盘的最小花费。

无

无

保证 $1 \leqslant k \leqslant n \leqslant 5 \times 10^5,$ $1 \leqslant a_i, b_i \leqslant 10^9$。 注：添加了 2 组 Hack 数据，如未通过将扣除 3 分。