勇者ビ太郎 2 (Bitaro the Brave 2)

勇者のビ太郎は，モンスターを討伐しに冒険に出ることになった．

ビ太郎は強さという値を持っている．ビ太郎の強さの初期値を \(x\) とする． モンスターは \(N\) 体存在し，\(1\) から \(N\) までの番号が付けられている．モンスター \(i\) (\(1 \leqq i \leqq N\)) を倒すには強さが \(A_i\) 以上であることが必要である．モンスター \(i\) を倒すと強さが\(B_i\) 増える．

ビ太郎は冒険において次のような行動をとることですべてのモンスターを倒したい．

• ある \(j\) (\(1 \leqq j \leqq N\)) から始めて，モンスター \(j, j + 1, \ldots, N\) を順に倒す．
• 次に，\(j \geqq 2\) なら，モンスター \(1, 2, \ldots, j-1\) を順に倒す．

モンスターの情報が与えられたとき，すべてのモンスターを倒すために必要な強さの初期値 \(x\) の最小値を求めるプログラムを作成せよ．

入力は以下の形式で標準入力から与えられる．

\(N\)
\(A_1\) \(A_2\) \(\dots\) \(A_N\)
\(B_1\) \(B_2\) \(\dots\) \(B_N\)

標準出力に，すべてのモンスターを倒すために必要な強さの初期値の最小値を \(1\) 行で出力せよ．

• \(2 \leqq N \leqq 500\,000\)．
• \(0 \leqq A_i \leqq 10^9\) (\(1 \leqq i \leqq N\))．
• \(0 \leqq B_i \leqq 10^9\) (\(1 \leqq i \leqq N\))．
• 入力される値はすべて整数である．

1. (\(10\) 点) \(N \leqq 2\,000\)，必要な強さの初期値の最小値は \(10\) 以下である．
2. (\(21\) 点) \(N \leqq 2\,000\)．
3. (\(19\) 点) 必要な強さの初期値の最小値は \(10\) 以下である．
4. (\(22\) 点) \(B_i = 1\) (\(1 \leqq i \leqq N\))．
5. (\(28\) 点) 追加の制約はない．

JOI 2025 · JCIOI · CC BY-SA 4.0