19428번 - Cute Panda 다국어

There are $n$ pandas numbered from $1$ to $n$, $i$-th of them has $a_i$ donuts. There are also $n$ bins numbered from $1$ to $n$, $i$-th of them can hold $b_i$ donuts. For any $i$ from $1$ to $n$, $i$-th panda can distribute his donuts to $i$-th and $(i \bmod n + 1)$-th bin.

Can you find a way to maximize the number of distributed donuts?

The input contains zero or more test cases, and is terminated by end-of-file. For each test case:

The first line contains an integer $n$ ($3 \leq n \leq 10^6$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq 10^9$).

The third line contains $n$ integers $b_1, b_2, \ldots, b_n$ ($0 \leq b_i \leq 10^9$).

It is guaranteed that the sum of all $n$ does not exceed $10^6$.

For each test case, output an integer which denotes the maximum number of distributed donuts.