B - 勇者ビ太郎 2 (Bitaro the Brave 2) 解説 /

実行時間制限: 1 sec / メモリ制限: 1024 MiB

Score: 100 points

Problem Statement

Bitaro, the brave hero, has set out on an adventure to defeat monsters.

Bitaro has a strength value, denoted as x, which starts at an initial value. There are N monsters, each labeled with a number from 1 to N. To defeat the i-th monster (1 \leq i \leq N), Bitaro must have a strength of at least A_i. Defeating the i-th monster increases Bitaro's strength by B_i.

Bitaro wants to defeat all the monsters using the following strategy:

  1. Start with a specific monster j (1 \leq j \leq N) and defeat the monsters in order: j, j + 1, \ldots, N.
  2. If j \geq 2, go back and defeat the monsters 1, 2, \ldots, j-1 in sequence.

Given the information about the monsters, write a program to determine the minimum initial strength x required for Bitaro to defeat all the monsters.

Input

Read the following data from the standard input.

N
A_1 A_2 \dots A_N
B_1 B_2 \dots B_N

Output

Output a single integer, the minimum initial strength x required for Bitaro to defeat all the monsters.

Constraints

  • 2 \leq N \leq 500\,000.
  • 0 \leq A_i \leq 10^9 (1 \leq i \leq N).
  • 0 \leq B_i \leq 10^9 (1 \leq i \leq N).
  • Given values are all integers.

Subtasks

  1. (10 points) N \leq 2\,000, and the minimum initial strength x is 10 or less.
  2. (21 points) N \leq 2\,000.
  3. (19 points) The minimum initial strength x is 10 or less.
  4. (22 points) B_i = 1 (1 \leq i \leq N).
  5. (28 points) No additional constraints.

Sample Input 1

5
1 3 2 8 6
4 3 1 1 2

Sample Output 1

1
  • Start with an initial strength of 1.
  • Defeat monsters in the following order:
    1. Defeat monster 1. Strength increases by 4 to 5.
    2. Defeat monster 2. Strength increases by 3 to 8.
    3. Defeat monster 3. Strength increases by 1 to 9.
    4. Defeat monster 4. Strength increases by 1 to 10.
    5. Defeat monster 5. Strength increases by 2 to 12.

This sample input satisfies the constraints of Subtasks 1,2,3 and 5.

Sample Input 2

5
1 6 3 3 2
1 2 1 0 1

Sample Output 2

3
  • Start with an initial strength of 3.
  • Defeat monsters in the following order:
    1. Defeat monster 3. Strength increases by 1 to 4.
    2. Defeat monster 4. Strength increases by 0 to 4.
    3. Defeat monster 5. Strength increases by 1 to 5.
    4. Defeat monster 1. Strength increases by 1 to 6.
    5. Defeat monster 2. Strength increases by 2 to 8.

This sample input satisfies the constraints of Subtasks 1,2,3 and 5.

Sample Input 3

10
11 9 8 12 7 7 8 12 9 10
1 1 1 1 1 1 1 1 1 1

Sample Output 3

9

This sample input satisfies the constraints of all the subtasks.

Sample Input 4

7
1125 638 0 37 737 820 1202
23 984 558 350 52 345 580

Sample Output 4

0

This sample input satisfies the constraints of Subtasks 1,2,3 and 5.

配点： 100 点

問題文

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

ビ太郎は強さという値を持っている．ビ太郎の強さの初期値を 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 点) 追加の制約はない．

入力例 1

5
1 3 2 8 6
4 3 1 1 2

出力例 1

1

強さの初期値が 1 であるとき，たとえば次のような順番ですべてのモンスターを倒すことができる．

  • 強さの初期値を 1 とする．
  • モンスター 1 を倒す．強さが 4 増えて，強さは 5 になる．
  • モンスター 2 を倒す．強さが 3 増えて，強さは 8 になる．
  • モンスター 3 を倒す．強さが 1 増えて，強さは 9 になる．
  • モンスター 4 を倒す．強さが 1 増えて，強さは 10 になる．
  • モンスター 5 を倒す．強さが 2 増えて，強さは 12 になる．

強さの初期値が 0 以下ですべてのモンスターを倒す方法は存在しないため，1 を出力する．

この入出力例は小課題 1,2,3,5 の制約を満たす．

入力例 2

5
1 6 3 3 2
1 2 1 0 1

出力例 2

3

強さの初期値が 3 であるとき，たとえば次のような順番ですべてのモンスターを倒すことができる．

  • 強さの初期値を 3 とする．
  • モンスター 3 を倒す．強さが 1 増えて，強さは 4 になる．
  • モンスター 4 を倒す．強さが 0 増えて，強さは 4 になる．
  • モンスター 5 を倒す．強さが 1 増えて，強さは 5 になる．
  • モンスター 1 を倒す．強さが 1 増えて，強さは 6 になる．
  • モンスター 2 を倒す．強さが 2 増えて，強さは 8 になる．

強さの初期値が 2 以下ですべてのモンスターを倒す方法は存在しないため，3 を出力する．

この入出力例は小課題 1,2,3,5 の制約を満たす．

入力例 3

10
11 9 8 12 7 7 8 12 9 10
1 1 1 1 1 1 1 1 1 1

出力例 3

9

この入出力例は小課題すべての制約を満たす．

入力例 4

7
1125 638 0 37 737 820 1202
23 984 558 350 52 345 580

出力例 4

0

この入出力例は小課題 1,2,3,5 の制約を満たす．