说明

时间限制：1 Sec 内存限制：256 MB 输入文件：gabbage.in 输出文件：gabbage.out

公园里有 $n$ 个垃圾，计划由 $n$ 名社区志愿者负责回收这些垃圾。

- 志愿者 $i(0 \le i \lt n)$ 的初始位置为坐标 $(a_i,0)$；

- 垃圾 $j(0 \le j \lt n)$ 的初始位置为坐标 $(x_j,y_j)$。

初始状态下，志愿者与垃圾均沿 $x$ 轴方向按顺序排列，即满足 $a_0 \le a_1 \le \ldots \le a_{n-1}$，且 $x_0 \le x_1 \le \ldots \le x_{n-1}$。

志愿者 $i$ 若要回收“垃圾 $j$、垃圾 $j+1$、……、垃圾 $i$”（其中 $0 \le j \le i$）这一连续区间内的所有垃圾，所需“劳力”等于“垃圾 $j$ 与志愿者 $i$ 的三次方距离”。

两点 $(x_0,y_0),(x_1,y_1)$ 的三次方距离定义为：$|x_0-x_1|^3+|y_0-y_1|^3$。

志愿者 $i$ 无法回收编号大于 $i$ 的垃圾；若志愿者 $i$ 不回收任何垃圾，其劳力为 $0$。

请设计回收方案，使回收所有垃圾的“总劳力”最小化。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_0,a_1,\ldots,a_{n-1}$。

第三行 $n$ 个整数 $x_0,x_1,\ldots,x_{n-1}$。

第四行 $n$ 个整数 $y_0,y_1,\ldots,y_{n-1}$。

输出格式

一个整数，表示回收所有垃圾的“总劳力”最小值。

样例

样例 1

4
0 1 2 3
0 1 2 3
1 1 1 1

4

样例说明：

最优方案是人 $i$ 回收垃圾 $i$。

每个垃圾对应的三次方距离等于 $1$，总和为 $4$。

样例 2

4
0 1 2 3
0 1 2 3
10 10 10 10

1027

样例说明：

最优方案是人 $3$ 回收全部垃圾，人 $0$、$1$、$2$ 不干活。

回收 $[0,3]$ 整段垃圾，代价由垃圾 $0$ 和人 $3$ 计算：$|3-0|^3+|0-10|^3 = 27+1000=1027$。

样例 3

4
0 1 2 3
0 1 2 3
2 2 2 2

18

样例说明：

最优方案是人 $1$ 回收垃圾 $0$、$1$，人 $3$ 回收垃圾 $2$、$3$；人 $0$、$2$ 不干活。

样例 4

10
3251 5690 6665 16359 20099 34165 44782 58006 70432 72049 
2772 9289 40088 44279 57294 57580 57685 61437 68039 73446 
64849 45751 58453 17408 55499 38832 58870 71951 66081 4577 

296036534625701

数据范围

对于 20% 的数据，$n \le 10$。

对于 40% 的数据，$n \le 1000$。

对于 100% 的数据，$1 \le n \le 3 \times 10^5$，$0 \le a_i,x_i,y_i \le 10^5$，$a_0 \le a_1 \le \ldots \le a_{n-1}$，$x_0 \le x_1 \le \ldots \le x_{n-1}$。