Background

Xiao Z, who loves "Ke science" (kexue), is doing a boring experiment.

Problem Description

In the laboratory, there is a circular track formed by $n$ connected experimental chambers. The $i$-th chamber is connected clockwise to the $(i+1)$-th chamber (in particular, the $n$-th chamber is connected to the $1$-st chamber). At the same time, there is a newly built chamber numbered $n+1$ that will be inserted into this circular track. It can be inserted between any two chambers that were originally adjacent.

The $i$-th chamber can transport a particle with charge amount $Q$ to its next chamber, and the energy cost of this process is $\vert Q \vert \times c_i$. In addition, the $i$-th chamber itself stores an amount $e_i$ of charge (the charge amount can be positive or negative). Due to the well-known law of conservation of charge, the charge stored in the $(n+1)$-th chamber and the algebraic sum of the total charge stored in the first $n$ chambers add up to $0$.

Xiao Z has a particle that originally has no charge. After the $(n+1)$-th chamber is inserted into the track, he will choose any chamber (including chamber $n+1$) as the starting point, put the particle into it, and make it travel clockwise for one full loop and return to the starting point driven by the chambers' energy. Every time the particle arrives at a chamber (including the starting point), the amount of charge it carries becomes the algebraic sum of its previous charge and the charge stored in that chamber.

Note: the charge amount is added with the chamber's stored charge first, and then the energy contribution is calculated.

Now, Xiao Z wants to know: among all ways of inserting the new chamber and choosing the starting point, what is the minimum energy required for the particle to complete one loop?

Input Format

The first line contains a positive integer $n$, representing the number of chambers originally on the circular track.

The second line contains $n+1$ non-negative integers, in order representing $c_1,c_2,...,c_{n+1}$.

The third line contains $n$ integers, in order representing $e_1,e_2,...,e_{n}$.

Output Format

Output one line containing one number, representing the minimum energy required for the particle to travel one full loop.

3
1 3 2 2
3 -5 1

9

12
4 7 7 8 8 4 5 5 9 10 1 1 10 
0 -5 7 8 1 -1 -6 8 2 4 10 8 

509

Hint

Explanation for Sample $1$: one optimal plan is to insert chamber $4$ between chamber $3$ and chamber $1$, choose chamber $4$ as the starting point, and the energy cost is $1\times 2\ +\ 4\times 1\ + \vert -1 \vert \times 3 \ +\ 0 \times 2 =9$.

This problem uses bundled Subtask testdata.

Special Property $\bf A$: for all $i\in[1,n+1](i\in \Z)$, $c_i=0$.

Special Property $\bf B$: for all $i\in[1,n+1](i\in \Z)$, $c_i=1$.

For $100\%$ of the data, $1\le n\le 2.5\times 10^5$, $0\le c_i\le 10^5$, $0\le |e_i|\le 10^5$.

It is guaranteed that the answer fits in the range of long long.

Translated by ChatGPT 5