DMOPC '18 Contest 4 P3 - Dr. Henri and Ionization

View as PDF

Submit solution


Points: 10 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

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, \ldots, a_N and b_1, b_2, \ldots, 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, \ldots, a_N.
The third line contains N space-separated integers, b_1, b_2, \ldots, 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).


Comments

There are no comments at the moment.