Overview

The work time \(T_i\) for each machine is always summed up for all machines, and the tool maintenance time \(R_i\) is only unnecessary for the “last machine worked on.” Therefore, the shortest time can be determined by simply considering “which machine to choose last.”

Analysis

When maintaining machines in some order, the flow of time is:

• Machine work: \(T\)
• (Except for the last) Tool maintenance: \(R\)
• Move to next machine…

The two important observations here are:

1. All \(T_i\) are always summed regardless of the order
   No matter the order, since each machine is worked on exactly once, the total work time is always \(\sum T_i\).

2. \(R_i\) does not occur only for the “last machine worked on”
   After the last machine, there is no next task, so tool maintenance is unnecessary.
   In other words, the total tool maintenance time that occurs is
   [ \sum Ri - R{\text{last}} ] (where \(R_{\text{last}}\) is the \(R\) of the machine chosen last).

Therefore, the total time is [ \sum T_i + \left(\sum Ri - R{\text{last}}\right) ] To minimize this, we should maximize the subtracted value \(R_{\text{last}}\), so the optimal choice is to make the machine with the largest \(R_i\) the last one.

Naively trying all orderings (\(N!\) permutations) is impossible when \(N \le 2\times 10^5\). However, due to the above observation, we don’t need to consider all orderings — we can solve it simply by “making the largest \(R_i\) the last.”

Example: When \((T,R)=(3,5),(10,2),(4,7)\)
[ \sum T=17,\ \sum R=14,\ \max R=7 ] The shortest time is [ 17+14-7=24 ] (Just make the machine with \(R=7\) the last one.)

Algorithm

1. Compute \(\text{sum\_t} = \sum T_i\)
2. Compute \(\text{sum\_r} = \sum R_i\)
3. Find \(\text{max\_r} = \max R_i\)
4. Output the answer as [ \text{sum_t} + \text{sum_r} - \text{max_r} ]

Complexity

• Time complexity: \(O(N)\) (only a single pass to compute sums and maximum)
• Space complexity: \(O(1)\) (only aggregate values are stored, no need to keep the input)

Implementation Notes

• Since \(T_i, R_i\) can be up to \(10^9\) and \(N\) can be up to \(2\times 10^5\), the sum can be as large as approximately \(2\times 10^{14}\). Python’s int handles this safely, but in other languages, use 64-bit integers.

• There is no need to store all data in an array; it is sufficient to update sum_t, sum_r, and max_r while reading the input.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    sum_t = 0
    sum_r = 0
    max_r = 0
    for _ in range(N):
        t, r = map(int, input().split())
        sum_t += t
        sum_r += r
        if r > max_r:
            max_r = r
    print(sum_t + sum_r - max_r)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.