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?
Comet OJ