概要

各日の「収入−支出」の累積和を見て、旅行中に所持金が最も落ち込む点（累積和の最小値）を調べれば、必要な初期所持金 \(X\) の最小値が一発で求まります。
答えは「累積和の最小値を 0 以上に持ち上げるための金額」です。

考察

\(i\) 日目終了時点の所持金を式で表すと、

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

です。
問題の条件は「すべての \(i\) で \(\text{money}_i \ge 0\)」なので、

[ 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) ]

つまり、\(X\) は各日の累積和に対して必要な下限をすべて満たす必要があります。
このとき必要な最小の \(X\) は、累積和の最小値を \(\text{min\_prefix}\) として

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

となります（\(\text{min\_prefix} \le 0\) のとき）。
もし累積和が一度も負にならないなら \(\text{min\_prefix}=0\) なので \(X_{\min}=0\) です。

なぜこれで十分か

• 累積和が最も小さい日でも \(X+\text{min\_prefix}\ge0\) なら、他の日はそれ以上なので必ず非負。
• 逆に、そこを満たさないとその日に負になってしまう。

素朴解法との比較

例えば「\(X\) を 0,1,2,… と試してシミュレーション」すると、答えが大きい場合に非常に遅くなります。
一方、累積和の最小値だけ見れば 1 回の走査で済み、\(N \le 10^5\) に十分間に合います。

アルゴリズム

1. prefix = 0（累積和 \(\sum(A_i-B_i)\)）
2. min_prefix = 0（累積和の最小値）
3. 各日について
   
   • prefix += A_i - B_i
   • min_prefix = min(min_prefix, prefix)
4. 最後に -min_prefix を出力

これが最小の初期所持金です。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\)

実装のポイント

• 制約上、合計値は大きくなり得ますが Python の int ならオーバーフローの心配はありません。

• 「各日の途中（収入後・支出前）」は条件に含まれないので、A_i - B_i をまとめて累積すればOKです。

• min_prefix の初期値を 0 にしておくと、「最初から最後まで一度も減らないケース」で答えが自然に 0 になります。

  ソースコード

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()

---

この解説は gpt-5.3-codex によって生成されました。