分数: 300 分
问题陈述
高桥负责维护 N 工厂里的机器。高桥无法同时维护多台机器,必须维护所有机器 N 每个只加工一次。
维护 i第台机器正好需要 T_i 工作时间秒数。此外,在完成每台机器的维护后,高桥必须立即对所使用的工具进行清洁和维修(以下称为“工具维修”)。工具维修 i第台机器正好需要 R_i 秒。工具维修所需的时间由每台机器决定,而不取决于下一台机器的工作情况。所有维护和工具维修必须按顺序进行,不能并行进行。在工具维修完成之前,无法开始下一台机器的维护。
但是,对于最后维护的机器,由于之后没有机器可以工作,因此可以跳过工具维修(并且由于跳过它会导致较早的完成时间,因此始终会跳过)。
机器之间的行程时间可以忽略不计,下一个任务可以在上一个任务完成后立即开始。
也就是说,如果维护顺序是 (p_1, p_2, \ldots, p_N) (排列 (1, 2, \ldots, N)),完成所有维护所需的总时间为
\left(\sum_{k=1}^{N-1} (T_{p_k} + R_{p_k})\right) + T_{p_N}
高桥可以维持 N 按照他喜欢的任何顺序进行机器操作。如果他按时开始工作 0,查找所有机器维护完成的最早时间。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq T_i \leq 10^9
- 1 \leq R_i \leq 10^9
- 所有输入均为整数
输入
N T_1 R_1 T_2 R_2 \vdots T_N R_N
- 第一行包含一个整数 N 代表机器数量。
- 线 2 通过 N + 1 包含有关每台机器的信息。
- 的 (1 + i)-第行包含工作时间 T_i 需要维持 i第台机器和工具维修时间 维护该机器后需要 R_i ,以空格分隔。
输出
在一行上打印所有机器维护完成的最早时间。
示例输入 1
3 5 3 3 7 8 2
示例输出 1
21
示例输入 2
5 10 4 7 9 3 1 6 9 2 5
示例输出 2
47
示例输入 3
8 100 80 200 500 150 60 300 200 50 90 400 100 250 300 180 150
示例输出 3
2610