Prizes

The organizers of the IDDA Cup are arranging T-shirts for the final round, with $n$ gift- presenters and $n$ boxes at their disposal. Each gift-presenter is currently holding a specific number of T-shirts in their hands, and each box has a predetermined capacity for holding T-shirts. The number of T-shirts in the $i$-th gift-presenter’s hands is $a_i$ and the capacity of the $i$-th box is $b_i$. Currently the boxes are empty and organizers want to distribute the T-shirts that the gift-presenters hold to the boxes so that they can rest a bit. However, they cannot exceed the capacity of any box.

For each gift-presenter numbered from $1$ to $n$, the T-shirts that the $i$-th of them holds can be placed in the $i$-th and $(imodn+1)$-th box.

Find the maximum number of T-shirts that can be distributed into boxes, if organizers make the optimal distribution.

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\le n\le 10^6)$.

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

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

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

Output

For each test case, print in a new line the maximum number of T-Shirts that can be distributed into boxes.

Examples

Scoring

This task consists of the following subtasks. If all tests of a subtask are passed, you will earn points for that subtask.

1. ($15$ points): $n\le 10$, $a_i,b_i\le 10$;

2. ($25$ points): $n\le 10$, $a_i,b_i\le 100$;

3. ($60$ points): $noadditionalconstrains$;