다리 건설

넓은 강에 기둥 $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$