Building Bridges

Time limit3sMemory limit128 MB

Summary

Pick a subset containing the first and last pillars, pay (h_i-h_j)^2 for each bridge section and w_i for each skipped pillar, and minimize the total.

Level: Hard8 of 10
Topics: Dynamic programming, Greedy, Geometry
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Constraints

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

Examples8

Example 1
Input
```
6
3 8 7 1 6 6
0 -1 9 1 2 0
```
Expected output
```
17
```
Example 2
Input
```
2
0 0
5 5
```
Expected output
```
0
```

Example 3

Input

2
0 1000000
-1000000 -1000000

Expected output

1000000000000

Example 4
Input
```
5
7 7 7 7 7
-3 -3 -3 -3 -3
```
Expected output
```
-9
```

Example 5

Input

5
0 1000000 0 1000000 0
0 1000000 1000000 1000000 0

Expected output

Example 6

Input

10
1 2 3 4 5 6 7 8 9 10
100 100 100 100 100 100 100 100 100 100

Expected output

Example 7

Input

10
10 9 8 7 6 5 4 3 2 1
-5 -5 -5 -5 -5 -5 -5 -5 -5 -5

Expected output

-4

Example 8

Input

5
1000000 0 0 0 1000000
1000000 1000000 1000000 1000000 1000000

Expected output