33725번 - Bitaro the Brave 2 서브태스크다국어

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 ≤ i ≤ 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 ≤ j ≤ N$) and defeat the monsters in order: $j, j + 1, \dots , N$.
2. If $j ≥ 2$, go back and defeat the monsters $1, 2, \dots , 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.

Read the following data from the standard input.

$N$

$A_1$ $A_2$ $\dots$ $A_N$

$B_1$ $B_2$ $\dots$ $B_N$

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

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