[CEOI2017] Building Bridges

题目描述

有 $n$ 根柱子依次排列,每根柱子都有一个高度。第 $i$ 根柱子的高度为 $h_i$。 现在想要建造若干座桥,如果一座桥架在第 $i$ 根柱子和第 $j$ 根柱子之间,那么需要 $(h_i-h_j)^2$​​ 的代价。 在造桥前,所有用不到的柱子都会被拆除,因为他们会干扰造桥进程。第 $i$ 根柱子被拆除的代价为 $w_i$,注意 $w_i$ 不一定非负,因为可能政府希望拆除某些柱子。 现在政府想要知道,通过桥梁把第 $1$ 根柱子和第 $n$ 根柱子连接的最小代价。注意桥梁不能在端点以外的任何地方相交。

输入输出格式

输入格式


第一行一个正整数 $n$。 第二行 $n$ 个空格隔开的整数,依次表示 $h_1,h_2,\cdots,h_n$​​。 第三行 $n$ 个空格隔开的整数,依次表示 $w_1,w_2,\cdots,w_n$​​。

输出格式


输出一行一个整数表示最小代价,注意最小代价不一定是正数。

输入输出样例

输入样例 #1

6
3 8 7 1 6 6
0 -1 9 1 2 0

输出样例 #1

17

说明

对于 $100\%$ 的数据,有 $2\le n\le 10^5;0\le h_i,\vert w_i\vert\le 10^6$。