AT_joi2025ho_b 勇者ビ太郎 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 $ 行で出力せよ． ---

### 小課題 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 $ 点) 追加の制約はない． --- ### Sample Explanation 1 強さの初期値が $ 1 $ であるとき，たとえば次のような順番ですべてのモンスターを倒すことができる． - 強さの初期値を $ 1 $ とする． - モンスター $ 1 $ を倒す．強さが $ 4 $ 増えて，強さは $ 5 $ になる． - モンスター $ 2 $ を倒す．強さが $ 3 $ 増えて，強さは $ 8 $ になる． - モンスター $ 3 $ を倒す．強さが $ 1 $ 増えて，強さは $ 9 $ になる． - モンスター $ 4 $ を倒す．強さが $ 1 $ 増えて，強さは $ 10 $ になる． - モンスター $ 5 $ を倒す．強さが $ 2 $ 増えて，強さは $ 12 $ になる． 強さの初期値が $ 0 $ 以下ですべてのモンスターを倒す方法は存在しないため， $ 1 $ を出力する． この入出力例は小課題 $ 1,2,3,5 $ の制約を満たす． --- ### Sample Explanation 2 強さの初期値が $ 3 $ であるとき，たとえば次のような順番ですべてのモンスターを倒すことができる． - 強さの初期値を $ 3 $ とする． - モンスター $ 3 $ を倒す．強さが $ 1 $ 増えて，強さは $ 4 $ になる． - モンスター $ 4 $ を倒す．強さが $ 0 $ 増えて，強さは $ 4 $ になる． - モンスター $ 5 $ を倒す．強さが $ 1 $ 増えて，強さは $ 5 $ になる． - モンスター $ 1 $ を倒す．強さが $ 1 $ 増えて，強さは $ 6 $ になる． - モンスター $ 2 $ を倒す．強さが $ 2 $ 増えて，強さは $ 8 $ になる． 強さの初期値が $ 2 $ 以下ですべてのモンスターを倒す方法は存在しないため， $ 3 $ を出力する． この入出力例は小課題 $ 1,2,3,5 $ の制約を満たす． --- --- ### Sample Explanation 3 この入出力例は小課題すべての制約を満たす． ### Sample Explanation 4 この入出力例は小課題 $ 1,2,3,5 $ の制約を満たす． ### Constraints - $ 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 $ )． - 入力される値はすべて整数である．