A wide river has ~n~ pillars of possibly different heights standing out of the water. They are arranged in a straight line from one bank to the other. We would like to build a bridge that uses the pillars as support. To achieve this we will select a subset of pillars and connect their tops into sections of a bridge. The subset has to include the first and the last pillar.

The cost of building a bridge section between pillars ~i~ and ~j~ is ~(h_i - h_j)^2~ as we want to avoid uneven sections, where ~h_i~ is the height of the pillar ~i~. Additionally, we will also have to remove all the pillars that are not part of the bridge, because they obstruct the river traffic. The cost of removing the ~i^{th}~ pillar is equal to ~w_i~. This cost can even be negative—some interested parties are willing to pay you to get rid of certain pillars. All the heights ~h_i~ and costs ~w_i~ are integers.

What is the minimum possible cost of building the bridge that connects the first and last pillar?

Input

The first line contains the number of pillars, ~n~. The second line contains pillar heights ~h_i~ in the order, separated by a space. The third line contains ~w_i~ in the same order, the costs of removing pillars.

Output

Output the minimum cost for building the bridge. Note that it can be negative.

Constraints

• ~2 \le n \le 10^5~
• ~0 \le h_i \le 10^6~
• ~0 \le \left| w_i \right| \le 10^6~

Subtask 1 (30 points)

• ~n \le 1\,000~

Subtask 2 (30 points)

• optimal solution includes at most 2 additional pillars (besides the first and last)
• ~\left| w_i \right| \le 20~

Subtask 3 (40 points)

• no additional constraints

Sample Input 1

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

Sample Output 1

17