Overview

By looking at the prefix sums of “income − expenses” for each day and finding the point where the money on hand drops the most during the trip (the minimum value of the prefix sum), we can directly determine the minimum required initial amount of money \(X\).
The answer is “the amount needed to raise the minimum prefix sum to at least 0.”

Analysis

Expressing the money on hand at the end of day \(i\) as a formula:

[ \text{money}i = X + \sum{k=1}^{i}(A_k - B_k) ]

The problem’s condition is “\(\text{money}_i \ge 0\) for all \(i\),” so:

[ X + \sum_{k=1}^{i}(A_k - B_k) \ge 0 \quad (\forall i) ]

[ X \ge -\sum_{k=1}^{i}(A_k - B_k) \quad (\forall i) ]

In other words, \(X\) must satisfy the lower bound required by the prefix sum for every day.
The minimum required \(X\) is, letting \(\text{min\_prefix}\) be the minimum prefix sum:

[ X_{\min} = -\text{min_prefix} ]

(when \(\text{min\_prefix} \le 0\)).
If the prefix sum never becomes negative, then \(\text{min\_prefix}=0\), so \(X_{\min}=0\).

Why this is sufficient

• If \(X+\text{min\_prefix}\ge0\) even on the day when the prefix sum is smallest, then all other days have a larger prefix sum, so they are guaranteed to be non-negative.
• Conversely, if this condition is not satisfied, the money becomes negative on that day.

Comparison with a naive approach

For example, if you “try \(X = 0, 1, 2, \ldots\) and simulate,” it becomes extremely slow when the answer is large.
On the other hand, by just looking at the minimum prefix sum, a single pass suffices, which is more than fast enough for \(N \le 10^5\).

Algorithm

1. prefix = 0 (prefix sum \(\sum(A_i-B_i)\))
2. min_prefix = 0 (minimum value of the prefix sum)
3. For each day:
   • prefix += A_i - B_i
   • min_prefix = min(min_prefix, prefix)
4. Finally, output -min_prefix

This is the minimum initial amount of money.

Complexity

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

Implementation Notes

• Given the constraints, the total values can become large, but with Python’s int, there is no worry about overflow.

• “During the middle of each day (after income, before expenses)” is not part of the conditions, so it is fine to accumulate \(A_i - B_i\) together.

• By initializing min_prefix to 0, the answer naturally becomes 0 in the case where the prefix sum never decreases from start to finish.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    
    prefix = 0
    min_prefix = 0  # minimum of cumulative (A_i - B_i)
    
    for _ in range(N):
        a, b = map(int, input().split())
        prefix += a - b
        if prefix < min_prefix:
            min_prefix = prefix
    
    # Need X + min_prefix >= 0  =>  X >= -min_prefix
    print(-min_prefix)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.3-codex.