Description

There are $n$ pillars arranged in order, and each pillar has a height. The height of the $i$-th pillar is $h_i$.

Now we want to build several bridges. If a bridge is built between the $i$-th pillar and the $j$-th pillar, it costs $(h_i-h_j)^2$.

Before building bridges, all pillars that are not used will be demolished, because they would interfere with the construction process. The cost to demolish the $i$-th pillar is $w_i$. Note that $w_i$ is not necessarily non-negative, because the government may want some pillars to be demolished.

Now the government wants to know the minimum total cost to connect pillar $1$ and pillar $n$ using bridges. Note that bridges cannot intersect anywhere other than at their endpoints.

Input Format

The first line contains a positive integer $n$.

The second line contains $n$ space-separated integers, which are $h_1,h_2,\cdots,h_n$ in order.

The third line contains $n$ space-separated integers, which are $w_1,w_2,\cdots,w_n$ in order.

Output Format

Output one line with one integer, the minimum total cost. Note that the minimum total cost is not necessarily positive.

6
3 8 7 1 6 6
0 -1 9 1 2 0

17

Hint

For $100\%$ of the testdata, $2\le n\le 10^5;0\le h_i,\vert w_i\vert\le 10^6$.

Translated by ChatGPT 5