Overview

This is a problem where we need to maintain \(N\) machines in an appropriate order and find the shortest time until the maintenance of the last machine is completed.

Analysis

In this problem, we are given the maintenance time \(T_i\) and the subsequent tool preparation time \(R_i\) for each machine. The key point is that tool preparation is not required after maintaining the last machine.

A naive approach would be to try all permutations (using bit exhaustive search or next_permutation, etc.), but since \(N\) can be up to \(2 \times 10^5\), this is computationally infeasible (\(O(N!)\) is extremely large).

So how can we efficiently find the optimal order?

Here is an important observation: For all machines except the last one, it is optimal to perform maintenance in ascending order of tool preparation time \(R_i\).

Let’s think about why this is the case. For example, if we maintain two machines A\((T_A, R_A)\) and B\((T_B, R_B)\) in this order, the total time is: $\( (T_A + R_A) + (T_B) = T_A + R_A + T_B \)\( Conversely, if we go in the order B→A: \)\( (T_B + R_B) + (T_A) = T_B + R_B + T_A \)\( Which is faster depends on the relative sizes of \)R_A\( and \)R_B$. In other words, performing the one with the smaller tool preparation time first makes the overall time shorter.

Also, since tool preparation is not needed for the very last machine, we want to place the machine with the largest tool preparation time at the end.

Therefore, we can see that sorting the pairs \((R_i, T_i)\) in ascending order of \(R_i\) and performing maintenance in that order gives the shortest time.

Algorithm

1. Read \((T_i, R_i)\) for each machine.
2. Create a list of pairs \((R_i, T_i)\) and sort in ascending order of \(R_i\) (if \(R_i\) values are the same, ascending order of \(T_i\) is fine).
3. Perform maintenance on the machines in the sorted order.
   • For each machine, add \(T_i\).
   • If it is not the last machine, also add \(R_i\).
4. Output the total time.

Example

Sample input:

3
3 2
1 4
2 1

\((T_i, R_i)\): (3,2), (1,4), (2,1) Sorted by \((R_i, T_i)\): (1,2), (2,3), (4,1) → maintain machines 3, 1, 2 in this order

Timeline: - Machine 3: work time 2 seconds → end time 2, preparation time 1 second (total 3 seconds) - Machine 1: work time 3 seconds → end time 6, preparation time 2 seconds (total 8 seconds) - Machine 2: work time 1 second → end time 9 (no preparation needed)

The answer is 9 seconds.

Complexity

• Time complexity: \(O(N \log N)\) (dominated by sorting)
• Space complexity: \(O(N)\) (array to store input)

Implementation Notes

• Use sys.stdin.read for fast input reading.
• By using (R_i, T_i) as the sort key, we get stable results even when tool preparation times are the same.
• Be careful not to add tool preparation time for the last machine.

## Source Code

```python
import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    TR = [(int(data[2*i+1]), int(data[2*i+2])) for i in range(N)]
    
    # 各機械の (T_i, R_i) を扱う
    # 最後に工具整備は不要なので、最後の機械は R_i が大きい順にしたくない
    # つまり、最後以外は R_i の小さい順に並べるのが最適
    
    # (R_i, T_i) でソートして、R_i の小さい順に並べる
    TR.sort(key=lambda x: (x[1], x[0]))
    
    total = 0
    for i in range(N):
        T, R = TR[i]
        total += T
        if i != N - 1:
            total += R
            
    print(total)

if __name__ == "__main__":
    main()

---

This editorial was generated by qwen3-coder-480b.