Building Bridges

A wide river has $n$ pillars standing out of the water, and their heights may differ. The pillars stand in a straight line from one bank to the other. You want to build a bridge that rests on these pillars. To do that, pick a subset of the pillars and join the tops of consecutive picked pillars into bridge sections. The subset must contain the first pillar and the last pillar.

Building a section between two consecutive picked pillars $i$ and $j$ costs $(h_i - h_j)^2$, where $h_i$ is the height of pillar $i$. The square keeps the bridge from running steeply uphill or downhill. Every pillar left out of the bridge blocks river traffic and has to be removed. Removing pillar $i$ costs $w_i$. This cost can be negative, because some interested parties are willing to pay you to get certain pillars out of the way. All heights $h_i$ and all costs $w_i$ are integers.

Find the minimum possible total cost of a bridge that connects the first pillar to the last one.

The first line contains the number of pillars $n$. The second line contains the heights $h_i$ in order, separated by spaces. The third line contains the removal costs $w_i$ in the same order.

Print the minimum cost of building the bridge. The value can be negative.

• $2 \le n \le 10^5$
• $0 \le h_i \le 10^6$
• $|w_i| \le 10^6$