Dr. Henri has discovered a new element with exactly ~N~ electrons. He wishes to remove all ~N~ electrons from the sample molecule he has obtained. This new element is extremely curious. The electrons remain practically static and occupy a two-dimensional circle about the nucleus. In addition, the electrons are spaced out evenly about this circle. If any electrons are added or removed, they will shift to again be evenly spaced, but their order will remain the same. The electrons are labelled ~1~ to ~N~ based on their original order about the circle.

Dr. Henri has determined two ways to remove electrons. The first is to remove an individual electron. A cost ~a_i~ is incurred for removing electron ~i~ in this manner. The other method is to remove two oppositely arranged electrons simultaneously. Two electrons are oppositely arranged when there are the same number of electrons in either arc between them. If electrons ~i~ and ~j~ are removed like so, the cost ~b_i+b_j~ is incurred. Note that he can only use the second method when the number of electrons in the ring is even.

Dr. Henri has already determined the costs ~a_1, a_2, \dots, a_N~ and ~b_1, b_2, \dots, b_N~. Can you help Dr. Henri find the minimum total cost to remove the electrons?

Constraints

~1 \le a_i, b_i \le 1\,000~ for all ~1 \le i \le N~.

Subtask 1 [50%]

~1 \le N \le 2\,000~

Subtask 2 [50%]

~1 \le N \le 200\,000~

Input Specification

The first line contains one integer, ~N~.
The second line contains ~N~ space-separated integers, ~a_1, a_2, \dots, a_N~.
The third line contains ~N~ space-separated integers, ~b_1, b_2, \dots, b_N~.

Output Specification

Output a single integer, the minimum total cost.

Sample Input 1

6
8 6 6 6 6 6
4 8 8 4 8 8

Sample Output 1

32

Explanation for Sample 1

Dr. Henri can first remove electrons ~1~ and ~4~ at a cost of ~4+4~, as they are oppositely arranged. He then removes the rest individually at a total cost of ~6+6+6+6=24~. So the total cost is ~32~, which is minimal.

Sample Input 2

5
2 2 2 2 2
1 1 1 1 1

Sample Output 2

6

Explanation for Sample 2

Dr. Henri must first remove a single electron at a cost of ~2~. Then he can remove two pairs at a cost of ~(1+1)+(1+1)~.