Dr. Henri has discovered a new element with exactly electrons. He wishes to remove all 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 to 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 is incurred for removing electron 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 and are removed like so, the cost 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 and . Can you help Dr. Henri find the minimum total cost to remove the electrons?
for all .
Subtask 1 [50%]
Subtask 2 [50%]
The first line contains one integer, .
The second line contains space-separated integers, .
The third line contains space-separated integers, .
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
Explanation for Sample 1
Dr. Henri can first remove electrons and at a cost of , as they are oppositely arranged. He then removes the rest individually at a total cost of . So the total cost is , which is minimal.
Sample Input 2
5 2 2 2 2 2 1 1 1 1 1
Sample Output 2
Explanation for Sample 2
Dr. Henri must first remove a single electron at a cost of . Then he can remove two pairs at a cost of .