Bitaro the Brave 2

문제

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

Bitaro has a strength value, denoted as $xx$, which starts at an initial value. There are $NN$ monsters, each labeled with a number from $11$ to $NN$. To defeat the $ii$-th monster (1 ≤ i ≤ N), Bitaro must have a strength of at least $A_{i}A\_i$. Defeating the $ii$-th monster increases Bitaro’s strength by $B_{i}B\_i$.

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

1. Start with a specific monster $jj$ (1 ≤ j ≤ N) and defeat the monsters in order: $j,j+1,\dots ,Nj,\; j\; +\; 1,\; \backslash 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 $xx$ required for Bitaro to defeat all the monsters.

입력

Read the following data from the standard input.

$NN$

$A_{1}A\_1$ $A_{2}A\_2$ $\dots \backslash dots$ $A_{N}A\_N$

$B_{1}B\_1$ $B_{2}B\_2$ $\dots \backslash dots$ $B_{N}B\_N$

출력

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

5
1 3 2 8 6
4 3 1 1 2

1

5
1 6 3 3 2
1 2 1 0 1

3

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

9

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

0