Overview

When processing visitors one by one in order, you can determine the ending time of the last visitor by maintaining and updating only “when the current counter service will finish”.

Analysis

In this problem, the service start time \(S_i\) for visitor \(i\) is the earliest time that satisfies both:

• The service for the previous visitor has finished
• The visitor themselves has arrived

In other words, the start time is:

\(S_i = \max(\text{end time of previous visitor},\ A_i)\)

And the end time is:

\(S_i + B_i\)

---

The key insight here is that all we need is “the end time of service up to the previous visitor”.

For example, if the current scheduled end time of the counter is current_end, then for the next visitor \((A, B)\), there are two cases:

• current_end < A
  The visitor hasn’t arrived yet, so the counter becomes idle
  \(\rightarrow\) Wait for arrival, start at time \(A\), and finish at \(A + B\)

• current_end >= A
  The visitor has already arrived, so service starts immediately after the previous one ends
  \(\rightarrow\) End time is current_end + B

Thus, the update formula is:

• current_end = A + B (when the counter is idle and waiting)
• current_end += B (when a waiting visitor is served immediately)

---

Concrete Example

Consider the following input:

• Visitor 1: \((A_1, B_1) = (2, 3)\)
• Visitor 2: \((A_2, B_2) = (4, 5)\)
• Visitor 3: \((A_3, B_3) = (10, 2)\)

Processing in order:

1. Initially current_end = 0
2. Visitor 1 arrives at time 2
   The counter is free, so service starts at time 2 and ends at \(2+3=5\)
   current_end = 5
3. Visitor 2 arrives at time 4
   Visitor 2 has already arrived, and the counter becomes free at time 5
   Service starts at time 5 and ends at \(5+5=10\)
   current_end = 10
4. Visitor 3 arrives at time 10
   The counter becomes free exactly at this time, so service starts immediately and ends at \(10+2=12\)
   current_end = 12

The answer is \(12\).

---

Why a Naive Approach Doesn’t Work

If you simulate by advancing time one unit at a time and tracking “who is currently being served,” the time can exceed \(10^9\), which is far too slow.

However, in this problem, for each visitor we only need to
start from the larger of “the previous end time” and “their own arrival time”,
so processing each visitor one by one in \(O(N)\) is sufficient.

Algorithm

Let current_end represent “the time at which all visitors processed so far have finished being served.”

1. Initialize current_end = 0
2. For each visitor \((A_i, B_i)\) in order, do the following:
   • If current_end < A_i, the counter is idle until the visitor arrives
     \(\rightarrow\) current_end = A_i + B_i
   • Otherwise, the visitor has already arrived
     \(\rightarrow\) current_end += B_i
3. Output current_end at the end

This current_end is exactly the service end time of the last visitor.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(1)\)

Implementation Notes

• You don’t need to store the start time as a separate variable — updating only the end time is sufficient.

• Since \(A_i, B_i\) can be up to \(10^9\) and \(N\) can be up to \(2 \times 10^5\), the answer can be very large. Python’s integers handle this without issues.

• Since the input can be large, using input = sys.stdin.readline improves speed.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    current_end = 0

    for _ in range(N):
        A, B = map(int, input().split())
        if current_end < A:
            current_end = A + B
        else:
            current_end += B

    print(current_end)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.4-high.