Bridge Construction and Pillar Removal

There are n pillars arranged in a row, where the height of the i-th pillar is \(h_i\). The government plans to connect the first pillar and the n-th pillar by constructing a series of bridges. A bridge between pillar \(i\) and pillar \(j\) costs \((h_i - h_j)^2\) and the bridges must only touch at the endpoints (they cannot intersect anywhere else).

Before constructing any bridges, any pillar that is not used in the bridging process will be demolished. Demolishing the i-th pillar incurs a cost of \(w_i\) (note that \(w_i\) can be negative, meaning that the government may prefer to demolish certain pillars).

If you decide to keep a subset of pillars \(p_1=1, p_2, \dots, p_k=n\) (in strictly increasing order) for the bridges, the total cost is computed as:

[ \text{Total Cost} = \sum_{i=1}^{n} w_i + \left( \sum_{j=1}^{k-1} (h_{p_j} - h_{p_{j+1}})^2 - \sum_{p \in {p_1, p_2, \ldots, p_k}} w_p \right). ]

Your task is to choose the pillars to keep so that the total cost (demolition cost plus bridge construction cost) is minimized, and output this minimum cost. Note that the first and the last pillar must be kept.

inputFormat

The first line contains a single integer n (2 ≤ n ≤ 10⁵) — the number of pillars.

The second line contains n space-separated integers \(h_1, h_2, \dots, h_n\) representing the heights of the pillars.

The third line contains n space-separated integers \(w_1, w_2, \dots, w_n\) representing the demolition cost of each pillar. Note that \(w_i\) may be negative.

outputFormat

Output a single integer — the minimum total cost to connect the first and the n-th pillar.

sample

2
3 8
1 2

25