시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 1 1 1 100.000%

문제

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.

예제 입력 1

5
8 4 8 3 10
1 0 4 5 1
5
9 4 10 0 4
3 5 2 2 1

예제 출력 1

11
13