A wide river has n pillars of possibly dierent 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 (\(hi-hj \))^2 as we want to avoid uneven sections, where \(hi\) 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 trac. The cost of removing the \(i-th\) pillar is equal to \(wi\). This cost can even be negative—some interested parties are willing to pay you to get rid of certain pillars. All the heights \(hi\) and costs \(wi\) are integers.

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

Формат вхідних даних

The first line contains the number of pillars, n.
The second line contains pillar heights \(hi\) in the order, separated by a space.
The third line contains \(wi\) in the same order, the costs of removing pillars.
\(2 \le n \le 10^5\)
\(0 \le hi \le 10^6\)
\(0 \le abs(wi) \le 10^6\)

SUBTASK 1 (30 points)
\(n \le 1000\)

SUBTASK 2 (30 points)
optimal solution includes at most 2 additional pillars (besides the first and last)
\(abs(wi) \le 20\)

SUBTASK 3 (40 points)
no additional constraints

Формат вихідних даних

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

Приклад вхідних даних-1

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

Приклад вихідних даних-1

17