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

勇者のビ太郎は,モンスターを討伐しに冒険に出ることになった.
ビ太郎は強さという値を持っている.ビ太郎の強さの初期値をx とする.モンスターはN 体存在し,1
からN までの番号が付けられている.モンスターi (1 ≦i ≦N) を倒すには強さがAi 以上であることが必要
である.モンスターi を倒すと強さがBi 増える.
ビ太郎は冒険において次のような行動をとることですべてのモンスターを倒したい.
• あるj (1 ≦j ≦N) から始めて,モンスターj, j + 1, . . . , N を順に倒す.
• 次に,j ≧2 なら,モンスター1, 2, . . . , j −1 を順に倒す.
モンスターの情報が与えられたとき,すべてのモンスターを倒すために必要な強さの初期値x の最小値を求
めるプログラムを作成せよ.

• 2 ≦N ≦500 000.
• 0 ≦Ai ≦109 (1 ≦i ≦N).
• 0 ≦Bi ≦109 (1 ≦i ≦N).
• 入力される値はすべて整数である.

第24 回日本情報オリンピック(JOI 2024/2025) 本選
2025 年2 月2 日(オンライン開催)

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

入力は以下の形式で標準入力から与えられる.
N
A1 A2 . . . AN
B1 B2 . . . BN

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

생성자가 기록되지 않았습니다.

출처 JOI 2025 Final