Minimizing Energy Consumption in a Circular Lab

The laboratory has n experimental chambers arranged in a circle. In the original configuration, chamber \(i\) is connected clockwise to chamber \(i+1\) (with chamber \(n\) connecting to chamber \(1\)). A new chamber, labeled \(n+1\), is to be added into the circle. It can be inserted into the connection between any two consecutive original chambers.

Each original chamber \(i\) (\(1\le i\le n\)) has an energy transmission parameter \(c_i\) and stores a fixed charge \(e_i\) (which may be positive or negative). When a charged particle with charge \(Q\) is transported from chamber \(i\) to chamber \(i+1\) by chamber \(i\), the energy cost incurred is \(|Q| \times c_i\). Note that when a particle reaches any chamber (including the starting chamber) its charge is updated by adding the chamber's stored charge; that is, if the particle arrives with charge \(Q\) and the chamber stores \(e\), then the new charge becomes \(Q+e\), and if chamber \(i\) is an original chamber, the cost to leave it is \(|Q+e_i| \times c_i\>.

By charge‐conservation, the new chamber (chamber \(n+1\)) must store a charge that makes the total stored charge zero, so its stored charge is

[ e_{n+1} = -\sum_{i=1}^{n} e_i. ]

Initially, the particle has no charge (\(Q=0\)). After the new chamber is connected the particle is placed into one of the \(n+1\) chambers (its starting chamber is chosen arbitrarily), and then it travels clockwise through all chambers exactly once, returning to the start. The process in each visited chamber is as follows:

1. Upon arrival at a chamber, update the particle's charge: \(Q \mathrel{+}= e\) (where \(e\) is the stored charge in that chamber).
2. If the chamber is an original chamber (i.e. chamber \(1\) to \(n\)), it transports the particle to the next chamber at an energy cost of \(|Q| \times c_i\) (using the updated charge \(Q\)). The new chamber (chamber \(n+1\)) has no associated transport cost.

Your task is to choose both an insertion position for the new chamber and a starting chamber such that the total energy needed for the particle to complete one full cycle is minimized. Output the minimum energy required.

inputFormat

The first line contains an integer \(n\) \((1 \le n \le 2000)\), the number of original chambers.

The second line contains \(n\) space-separated integers \(e_1, e_2, \dots, e_n\), representing the charge stored in each original chamber (\(-10^9 \le e_i \le 10^9\)).

The third line contains \(n\) space-separated integers \(c_1, c_2, \dots, c_n\), where \(c_i\) \((0 \le c_i \le 10^9)\) is the energy cost factor for transporting a particle from chamber \(i\) to the next chamber.

outputFormat

Output a single integer: the minimum energy required for the particle to complete one full cycle under an optimal insertion and starting choice.

sample

1
5
2

0