← 返回题目列表

AtCoder · awc0087_b

B. 工厂机器维修

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

分数: 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