Overview

In an \(N\)-day trip, given the “income \(A_i\)” and “expenditure \(B_i\)” for each day, the problem asks to find the minimum initial amount of money \(X\) such that the amount of money held never becomes negative at the end of any day.

Approach

1. Express the amount of money at the end of each day as a formula

Let the initial amount of money be \(X\) yen. If we define the daily balance as \(D_i = A_i - B_i\), then the amount of money \(S_k\) immediately after processing day \(k\) can be expressed as: $\(S_k = X + (D_1 + D_2 + \dots + D_k)\)$

Here, \((D_1 + D_2 + \dots + D_k)\) is the cumulative sum of the daily balances from day \(1\) to day \(k\). If we denote this as \(C_k\), the condition is that for all \(k \in \{1, \dots, N\}\), the following must hold: $\(X + C_k \geq 0\)$

2. Rearrange the condition in terms of \(X\)

Rearranging the above inequality in terms of \(X\), we get: $\(X \geq -C_k\)$

Since this must hold for all \(k\), \(X\) must be at least the maximum of \(-C_k\). Additionally, since the problem states that \(X\) must be a non-negative integer, the final answer is: $\(\text{Minimum } X = \max(0, \max_{1 \leq k \leq N} (-C_k))\)$

3. Concrete example

For example, consider the case where the daily balances \(A_i - B_i\) are +2, -5, +1 in order. - Cumulative balance at end of day 1: \(C_1 = +2\) - Cumulative balance at end of day 2: \(C_2 = 2 - 5 = -3\) - Cumulative balance at end of day 3: \(C_3 = -3 + 1 = -2\)

In this case, the values of \(-C_k\) are -2, 3, 2, and the maximum is \(3\). If the initial amount is \(X=3\), the amounts at the end of each day are \(5, 0, 1\), which never become negative. If \(X=2\), the amount becomes \(-1\) on day 2, so the minimum value is \(3\).

Algorithm

We can solve this efficiently by tracking the minimum cumulative balance.

1. Initialize the current cumulative balance (excluding initial money) current_diff to \(0\), and the minimum cumulative balance so far min_diff to \(0\).
2. For \(i = 1\) to \(N\), repeat the following:
   • Compute the daily balance \(D_i = A_i - B_i\).
   • Add \(D_i\) to current_diff.
   • If current_diff is less than min_diff, update min_diff.
3. If the minimum cumulative balance is, for example, \(-3\), then \(X=3\) is needed to offset it. Therefore, output \(\max(0, -min\_diff)\).

Complexity

• Time complexity: \(O(N)\)
  • Since we scan through the \(N\) days of data once, the computation finishes in time proportional to the input size. With \(N=10^5\), this is sufficiently fast.
• Space complexity: \(O(N)\) or \(O(1)\)
  • \(O(N)\) if all input values are stored in a list, \(O(1)\) if read incrementally.

Implementation Notes

• Handling large values: Since \(A_i, B_i\) can be up to \(10^9\) and \(N\) is \(10^5\), the cumulative balance can reach approximately \(10^{14}\). In Python, there is no limit on integer size so it can be computed directly, but in other languages (such as C++) you need to use a 64-bit integer type (long long, etc.).

• Speeding up input: Since \(N\) can be large, reading all input at once using sys.stdin.read().split() or similar methods can reduce execution time.

  Source Code

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白で分割してリスト化します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # イテレータを使用してデータを順番に取得します
    it = iter(input_data)
    N = int(next(it))
    
    # current_diff は、初期所持金 X を除いた i 日目終了時点の累積収支を表します
    current_diff = 0
    # min_diff は、累積収支の最小値を保持します
    min_diff = 0
    
    for _ in range(N):
        A = int(next(it))
        B = int(next(it))
        # i 日目の収支 (A_i - B_i) を累積収支に加算します
        current_diff += (A - B)
        # 累積収支がこれまでの最小値を下回った場合、更新します
        if current_diff < min_diff:
            min_diff = current_diff
            
    # すべての i 日目において X + (i日目までの累積収支) >= 0 である必要があります
    # つまり、X >= -(i日目までの累積収支) がすべての i で成り立つ必要があります
    # したがって、X は 0 以上かつ max(0, -min_diff) 以上である必要があります
    print(max(0, -min_diff))

if __name__ == '__main__':
    solve()

---

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