B - Factory Machine Maintenance Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

高橋君は工場で N 台の機械のメンテナンスを担当しています。高橋君は同時に複数の機械のメンテナンスを行うことはできず、N 台すべての機械をちょうど 1 回ずつメンテナンスしなければなりません。

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
  • 1 行目には、機械の台数を表す整数 N が与えられる。
  • 2 行目から N + 1 行目には、各機械の情報が与えられる。
  • 1 + i 行目には、i 番目の機械のメンテナンスにかかる作業時間 T_i と、その機械のメンテナンス後に必要な工具整備時間 R_i が、スペース区切りで与えられる。

出力

すべての機械のメンテナンスが完了する最も早い時刻を 1 行で出力してください。

入力例 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

Score : 300 pts

Problem Statement

Takahashi is in charge of maintaining N machines at a factory. Takahashi cannot maintain multiple machines simultaneously and must maintain all N machines exactly once each.

Maintaining the i-th machine takes exactly T_i seconds of work time. Additionally, immediately after completing the maintenance of each machine, Takahashi must perform cleaning and servicing of the tools used (hereafter called "tool servicing"). Tool servicing for the i-th machine takes exactly R_i seconds. The time required for tool servicing is determined by each machine and does not depend on which machine is worked on next. All maintenance and tool servicing must be performed sequentially and cannot be done in parallel. The next machine's maintenance cannot begin until tool servicing is complete.

However, for the last machine to be maintained, since there is no machine to work on afterward, tool servicing can be skipped (and since skipping it results in an earlier completion time, it is always skipped).

Travel time between machines is negligible, and the next task can begin immediately after the previous one finishes.

That is, if the order of maintenance is (p_1, p_2, \ldots, p_N) (a permutation of (1, 2, \ldots, N)), the total time required to complete all maintenance is

\left(\sum_{k=1}^{N-1} (T_{p_k} + R_{p_k})\right) + T_{p_N}

Takahashi can maintain the N machines in any order he likes. If he starts working at time 0, find the earliest time at which all machine maintenance is completed.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq T_i \leq 10^9
  • 1 \leq R_i \leq 10^9
  • All inputs are integers

Input

N
T_1 R_1
T_2 R_2
\vdots
T_N R_N
  • The first line contains an integer N representing the number of machines.
  • Lines 2 through N + 1 contain information about each machine.
  • The (1 + i)-th line contains the work time T_i required to maintain the i-th machine and the tool servicing time R_i required after maintaining that machine, separated by a space.

Output

Print the earliest time at which all machine maintenance is completed, on a single line.

Sample Input 1

3
5 3
3 7
8 2

Sample Output 1

21

Sample Input 2

5
10 4
7 9
3 1
6 9
2 5

Sample Output 2

47

Sample Input 3

8
100 80
200 500
150 60
300 200
50 90
400 100
250 300
180 150

Sample Output 3

2610