题目描述

你是一个在三维空间中的生命。

你的任务是摧毁一维世界的整条时间线。

时间线由 $n$ 个时刻构成，按顺序编号为 $1\sim n$ 。 为了摧毁时间线，你早已安插了一枚 E.Space 和三个控制器。三个控制器分别叫做 Past，Present 和 Future 。

你并没有足够强大的力量，你只能通过随机逐个地移除时刻的方式来完成任务。每个时刻和相邻的时刻都有一定的连结，而改变这样的联系就需要花费与之相关的能量。你需要花费的能量为要移除的时刻和相邻两个时刻中 E.Space 的位置到下一个时刻中对应控制器的位置的平方和。形式化地，设 E.Space 在第 $i$ 个时刻的位置为 $a_i$ ，Past 控制器在第 $i$ 个时刻的位置为 $x_i$ ，Present 控制器在第 $i$ 个时刻的位置为 $y_i$ ，Future 控制器在第 $i$ 个时刻的位置为 $z_i$ ，那么移除第 $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$ 。

第二行 $n$ 个整数，第 $i$ 个表示 $a_i$ 。

第三行 $n$ 个整数，第 $i$ 个表示 $x_i$ 。

第四行 $n$ 个整数，第 $i$ 个表示 $y_i$ 。

第五行 $n$ 个整数，第 $i$ 个表示 $z_i$ 。

输出格式

一行一个整数，表示答案。

样例

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

5

数据范围与提示

保证 $1\le n\le 60$ 。

保证所有输入的数的绝对值不超过 $10^3$ 。

子任务 1（7分）：$n\le 9$

子任务 2（11分）：$n\le 20$

子任务 3（13分）：$z_i=0$

子任务 4（22分）：$\forall 1\le i < n,~z_i\ge z_{i+1}\ge 0$

子任务 5（22分）：$n\le 40$

子任务 6（25分）：无特殊限制