A wide river has 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 and is as we want to avoid uneven sections, where is the height of the pillar . 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 pillar is equal to . This cost can even be negative—some interested parties are willing to pay you to get rid of certain pillars. All the heights and costs 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, . The second line contains pillar heights in the order, separated by a space. The third line contains in the same order, the costs of removing pillars.
Output the minimum cost for building the bridge. Note that it can be negative.
Subtask 1 (30 points)
Subtask 2 (30 points)
- optimal solution includes at most 2 additional pillars (besides the first and last)
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