题目描述

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

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

时间线由 $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$。

输出格式

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

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

5

9
-254 -877 272 404 786 -744 -284 -868 629
10 -396 -329 265 299 377 -607 575 798
-738 -94 -550 -440 -80 -363 -85 -287 377
-99 -401 -304 -344 -995 845 -191 -302 -533

21474759

60
429 -821 -652 24 263 -192 918 61 282 -629 -834 495 565 975 863 -207 -825 -783 -352 88 186 332 -750 -243 -697 871 946 658 853 -708 -452 566 171 364 379 630 -545 110 250 861 -838 490 -14 463 479 343 240 940 -935 325 818 -833 611 -419 -4 972 189 120 -592 -241
372 794 673 524 656 -386 -851 -728 -515 -439 -424 -300 -777 117 -731 26 727 -431 -482 -428 970 559 -343 48 -843 -379 -4 -272 767 -742 -280 0 -230 -808 608 23 208 -596 811 -428 -905 -467 208 -929 -374 -110 949 27 201 -823 -552 -105 -47 250 -435 841 879 -128 -245 -100
655 984 -425 -502 -344 415 70 -146 -780 611 272 607 723 -249 -869 -651 598 278 997 223 -336 -633 461 -115 591 892 950 -964 533 401 -986 -641 689 214 539 432 773 -498 -684 -946 -812 -370 -286 -382 46 184 950 151 245 -696 789 -883 493 -321 505 806 624 -551 914 -827
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

193466852

提示

保证 $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）： 无特殊限制。