다리 건설

시간 제한3초메모리 제한128 MB

요약

첫 기둥과 마지막 기둥을 반드시 포함하는 부분집합을 골라 인접한 두 기둥 사이 구간 비용 (h_i-h_j)^2과 빠진 기둥마다 w_i를 지불할 때 최소 총비용을 구한다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 그리디, 기하
정답자: 아직 제출이 없습니다

문제

넓은 강에 기둥 $n$ 개가 물 위로 솟아 있다. 기둥의 높이는 서로 다를 수 있고, 기둥은 한쪽 강기슭에서 반대쪽 강기슭까지 일직선으로 늘어서 있다. 이 기둥을 지지대로 삼아 다리를 놓으려고 한다. 기둥 중 일부를 고른 다음, 고른 기둥 가운데 이웃한 두 기둥의 꼭대기를 이어 다리 구간을 만든다. 고른 기둥에는 첫 번째 기둥과 마지막 기둥이 반드시 들어간다.

이웃한 두 기둥 $i$ 와 $j$ 를 잇는 구간을 놓는 비용은 $(h_i - h_j)^2$ 이다. $h_i$ 는 기둥 $i$ 의 높이이고, 이 비용은 기울기가 심한 구간을 피하려는 데서 나온다. 다리에 쓰이지 않은 기둥은 강의 통행을 막으므로 모두 뽑아내야 한다. $i$ 번 기둥을 뽑는 비용은 $w_i$ 이다. 이 비용은 음수일 수도 있다. 특정 기둥이 없어지기를 바라는 쪽에서 오히려 돈을 주기도 하기 때문이다. 모든 높이 $h_i$ 와 비용 $w_i$ 는 정수이다.

첫 번째 기둥과 마지막 기둥을 잇는 다리를 놓는 최소 비용을 구하라.

입력

첫째 줄에 기둥의 개수 $n$ 이 주어진다. 둘째 줄에 기둥의 높이 $h_i$ 가 순서대로 공백으로 구분되어 주어진다. 셋째 줄에 같은 순서로 기둥을 뽑는 비용 $w_i$ 가 주어진다.

출력

다리를 놓는 최소 비용을 출력한다. 이 값은 음수일 수도 있다.

제한

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

예제8

예제 1
입력
```
6
3 8 7 1 6 6
0 -1 9 1 2 0
```
예상 출력
```
17
```
예제 2
입력
```
2
0 0
5 5
```
예상 출력
```
0
```

예제 3

입력

2
0 1000000
-1000000 -1000000

예상 출력

1000000000000

예제 4
입력
```
5
7 7 7 7 7
-3 -3 -3 -3 -3
```
예상 출력
```
-9
```

예제 5

입력

5
0 1000000 0 1000000 0
0 1000000 1000000 1000000 0

예상 출력

예제 6

입력

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

예상 출력

예제 7

입력

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

예상 출력

-4

예제 8

입력

5
1000000 0 0 0 1000000
1000000 1000000 1000000 1000000 1000000

예상 출력