You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小梓是一个极度谨慎的人，不管去哪里都会带好武器，在居住的地方布置陷阱，做好完全的战斗准备。

这一次的露营也不例外，小梓在营地附近布置了一排地雷。这排地雷由 $n$ 个小地雷组成，编号从 $1$ 到 $n$，小梓想知道如果有敌人前来，他要花多少的代价才能拆除这些地雷。

在拆除地雷时，可以任意选择拆除的顺序，每次只能拆除一个地雷，且拆除一个地雷后，这个地雷左右两侧的地雷会连接到一起。每个地雷有 $4$ 个属性 $p_i, q_i, r_i, s_i$，排除第 $i$ 个地雷的代价为 $(p_{i−1} − q_i)^2 + (p_i − r_{i+1})^2 + (p_{i+1} − s_{i+2})^2$，其中 $(i − 1)$ 为当前时刻 $i$ 左侧的地雷， $i + 1, i + 2$ 同理。如果这样的地雷不存在则对应的 $p_i, q_i, r_i, s_i$均为 $0$。敌人无法知道地雷的内部顺序，只能随便按照某个顺序进行拆除。小梓想知道，在最坏的情况下，敌人需要花多少代价才能拆除所有地雷。

输入格式

接下来的输入为：

第一行一个整数 $n$ 表示地雷数。

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

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

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

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

输出格式

一行一个整数表示答案。

样例输入1

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

样例输出1

8

【样例 2】

参见下发文件。

数据规模和约定

对于所有数据，满足 $1 \leq n \leq 70$, $-1000 \leq p_i, q_i, r_i, s_i \leq 1000$。

样例解释

依次拆除编号为 $3, 1, 2, 4$ 的地雷时代价最大。