题目描述

你是一个在三维空间中的生命，任务是在一维世界中摧毁一条时间线。时间线由 $n$ 个时刻构成，按顺序编号为 $1 \sim n$。

你安插了一枚 E.Space 和三个控制器（Past, Present, Future）。只能通过随机逐个地移除时刻的方式来摧毁时间线。

移除第 $i$ 个时刻消耗的能量为： [ (a_{i-1} - x_i)^2 + (a_i - y_{i+1})^2 + (a_{i+1} - z_{i+2})^2 ] 其中下标在 $[1, n]$ 之外的值为 $0$。

移除一个时刻后，相邻的时刻会合在一起：移除第 $i$ 个时刻后，原来的第 $i+1$ 个时刻变成第 $i$ 个时刻，第 $i+2$ 个时刻变成第 $i+1$ 个时刻，以此类推。

问：在最坏情况下（即按照使总能量最大的顺序移除时刻），移除整条时间线最多需要多少能量。

输入格式

• 第一行：$n$
• 第二行：$a_1, a_2, ..., a_n$
• 第三行：$x_1, x_2, ..., x_n$
• 第四行：$y_1, y_2, ..., y_n$
• 第五行：$z_1, z_2, ..., z_n$

样例

输入：

4
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1

输出：

5

数据范围

• $1 \le n \le 60$
• 所有输入值的绝对值 $\le 10^3$
• 时间限制：1000ms
• 内存限制：256MB