P15001 摧毁时间线

你是一个在三维空间中的生命。 你的任务是摧毁一维世界的整条时间线。 时间线由 $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_{id_{i-1}}-x_{id_i})^2+(a_{id_i}-y_{id_{i+1}})^2+(a_{id_{i+1}}-z_{id_{i+2}})^2$，其中 $id_i$ 表示目前从前往后第 $i$ 个时刻的编号。特殊地，下标在 $[1,n]$ 之外的所有值视为 $0$。 在移除一个时刻后，由于强烈的引力，和时刻 $i$ 相邻的两个时刻会重新靠在一起。 你想知道在运气最不好的情况下，移除整条时间线最多需要多少能量。

第一行一个正整数 $n$。 第二行 $n$ 个整数，第 $i$ 个表示 $a_i$。 第三行 $n$ 个整数，第 $i$ 个表示 $x_i$。 第四行 $n$ 个整数，第 $i$ 个表示 $y_i$。 第五行 $n$ 个整数，第 $i$ 个表示 $z_i$。

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

保证 $1\le n\le 60$。 保证所有输入的数的绝对值不超过 $10^5$。 子任务 1（7 pts）： $n\le 9$。 子任务 2（11 pts）： $n\le 20$。 子任务 3（13 pts）： $z_i=0$。 子任务 4（22 pts）： $\forall 1\le i < n,~z_i\ge z_{i+1}\ge 0$。 子任务 5（22 pts）： $n\le 40$。 子任务 6（25 pts）： 无特殊限制。