Overview

When maintaining \(N\) machines, each machine requires a work time \(T_i\) followed by a servicing time \(R_i\). However, the last machine worked on does not require servicing time. The problem asks us to find the minimum total time to complete all work by optimizing the order of operations.

Analysis

1. Breaking Down the Total Time

Regardless of the order in which machines are maintained, the following times always occur: - Maintenance time for all machines: \(T_1 + T_2 + \dots + T_N\) - Servicing time for all machines except the last one: \(R_i\) (for \(N-1\) machines)

The total time can be expressed as follows: $\(\text{Total time} = \sum_{i=1}^{N} T_i + \sum_{i \in \text{all except last}} R_i\)$

2. Strategy for Minimization

The sum of all \(T_i\) does not change regardless of the maintenance order. Therefore, to minimize the total time, we need to minimize the “sum of servicing times excluding the last machine”.

If we denote the sum of all servicing times as \(\sum R_i\), then the “sum of servicing times excluding the last machine” can be rewritten as: $\(\sum_{i \in \text{all except last}} R_i = (\sum_{i=1}^{N} R_i) - R_{\text{last machine}}\)$

To minimize this value, we can see that we should maximize \(R_{\text{last machine}}\), the value being subtracted.

3. Conclusion

1. Sum up all \(T_i\).
2. Sum up all \(R_i\).
3. Find the maximum value among all \(R_i\).
4. The answer is “\(\text{sum of } T + \text{sum of } R - \text{maximum } R\)”.

Algorithm

1. Prepare variables total_t, total_r, max_r, and initialize each to 0.
2. For each of the \(N\) machines, read the input and repeat the following:
   • Add \(T_i\) to total_t.
   • Add \(R_i\) to total_r.
   • Compare max_r with \(R_i\) and update max_r with the larger value.
3. Compute and output total_t + total_r - max_r.

Complexity

• Time complexity: \(O(N)\)
  • We only need to scan the information of \(N\) machines once, so computation is possible in linear time.
• Space complexity: \(O(N)\)
  • If all input data is stored in a list or similar structure, it is \(O(N)\). If processed one at a time, it can be reduced to \(O(1)\).

Implementation Notes

• Handling large numbers: Since \(T_i\) and \(R_i\) can be up to \(10^9\) and \(N\) can be \(2 \times 10^5\), the total can exceed \(10^{14}\). In Python, there is no limit on integer size so this is not an issue, but in other languages (such as C++) you need to use 64-bit integer types (long long, etc.).

• Fast I/O: Since \(N\) can be large and the amount of data may be significant, it is safer to use methods like sys.stdin.read().split() to handle input speed efficiently.

  Source Code

import sys

def solve():
    # 入力をすべて取得
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    
    total_t = 0
    total_r = 0
    max_r = 0
    
    # 各機械の情報を処理
    for i in range(N):
        t = int(input_data[2 * i + 1])
        r = int(input_data[2 * i + 2])
        
        total_t += t
        total_r += r
        if r > max_r:
            max_r = r
            
    # 全体の時間は (全てのTの合計) + (最後の機械以外のRの合計)
    # これは (全てのTの合計) + (全てのRの合計) - (最後に持ってくる機械のR) と等しい
    # 最短時間を求めるには、最後に持ってくる機械のRを最大にすればよい
    ans = total_t + total_r - max_r
    print(ans)

if __name__ == "__main__":
    solve()

---

This editorial was generated by gemini-3-flash-thinking.