Overview

For each day, all we need is whether the “amount of money at the end of that day” is \(0\) or more, so it suffices to look only at the difference \(A_i - B_i\) for each day. By finding the minimum value of the prefix sum of these differences, we can determine the minimum initial amount of money needed.

Analysis

Let \(X\) yen be the amount of money at the start of the trip.

Define the cumulative balance up to day \(i\) as

\(P_i = \sum_{j=1}^{i}(A_j - B_j)\)

Then the amount of money at the end of day \(i\) is

\(X + P_i\)

This value must be \(0\) or more for all \(i\), so the condition is

\(X + P_i \geq 0 \quad (1 \leq i \leq N)\)

In other words,

\(X \geq -P_i \quad (1 \leq i \leq N)\)

Therefore, the minimum \(X\) needed to satisfy all days is, letting \(\min P\) be the smallest value among \(P_i\):

\(X = -\min P\)

However, since the initial amount of money must be \(0\) or more, if the prefix sum never becomes negative, the answer is \(0\). To handle this naturally, we include the initial prefix sum of \(0\) when taking the minimum, which is why in the code we start with min_s = 0.

Key Insight

In this problem, we only need to check the state right after all processing for that day is complete, not during the middle of each day’s processing. Therefore, there is no need to consider income \(A_i\) and expenses \(B_i\) separately — the daily net change \(A_i - B_i\) is sufficient.

Why a Naive Approach is Not Good

For example, one might consider trying various initial amounts \(X\) and simulating each time. However, trying answers one by one is obviously infeasible, and even using binary search would be overkill for this problem.

In reality, all we need is “how far the prefix sum drops,” which can be determined in a single pass.

Concrete Example

For example, suppose the values of \(A_i - B_i\) for each day are

\(-3,\ +5,\ -4\)

Then the prefix sums are:

• After day 1: \(-3\)
• After day 2: \(2\)
• After day 3: \(-2\)

The minimum is \(-3\). Therefore, the minimum initial amount of money needed is \(3\) yen.

Indeed, if \(X=3\), the amount of money after each day is:

• After day 1: \(3 + (-3) = 0\)
• After day 2: \(3 + 2 = 5\)
• After day 3: \(3 + (-2) = 1\)

All values are \(0\) or more.

Algorithm

1. Initialize the cumulative balance s to \(0\).
2. Initialize the minimum cumulative balance min_s to \(0\).
3. For each day, compute s += A_i - B_i.
4. Each time, update min_s = min(min_s, s).
5. Finally, output -min_s.

If min_s is negative, you need to start with that absolute value of money. If min_s is \(0\) or more, an initial amount of \(0\) yen is sufficient.

Complexity

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

Implementation Notes

• To account for the initial state when taking the minimum, we start with min_s = 0.

• Since we only need to check the amount of money after each day ends, not during the middle of a day, it suffices to simply accumulate \(A_i - B_i\).

• \(A_i, B_i\) can be up to \(10^9\), but in Python there is no need to worry about integer overflow.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    s = 0
    min_s = 0
    for _ in range(N):
        a, b = map(int, input().split())
        s += a - b
        if s < min_s:
            min_s = s
    print(-min_s)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.4-high.