一条宽阔的河流中有 $n$ 根高度可能各不相同的柱子矗立在水中。它们从河的一岸到另一岸排成一条直线。我们想要建造一座桥，利用这些柱子作为支撑。为了实现这一目标，我们将选择一个柱子子集，并将它们的顶部连接成桥梁的各个部分。该子集必须包含第一根和最后一根柱子。

在柱子 $i$ 和 $j$ 之间建造一段桥梁的成本为 $(h_i - h_j)^2$，因为我们希望避免不平整的桥段，其中 $h_i$ 是柱子 $i$ 的高度。此外，我们还必须移除所有不属于桥梁的柱子，因为它们会阻碍河流交通。移除第 $i$ 根柱子的成本等于 $w_i$。这个成本甚至可以是负数——一些相关方愿意付钱让你移除某些柱子。所有的柱子高度 $h_i$ 和移除成本 $w_i$ 均为整数。

请问连接第一根和最后一根柱子的桥梁的最小可能成本是多少？

输入格式

第一行包含柱子的数量 $n$。第二行包含按顺序排列的柱子高度 $h_i$，以空格分隔。第三行包含按顺序排列的移除柱子的成本 $w_i$。

输出格式

输出建造桥梁的最小成本。注意，该成本可能是负数。

数据范围

• $2 \le n \le 10^5$
• $0 \le h_i \le 10^6$
• $0 \le |w_i| \le 10^6$

子任务

• 子任务 1（30 分）：$n \le 1000$
• 子任务 2（30 分）：最优解包含最多 2 根额外柱子（除了第一根和最后一根），且 $|w_i| \le 20$
• 子任务 3（40 分）：无额外限制

样例

输入 1

6
3 8 7 1 6 6
0 -1 9 1 2 0

输出 1

17