4217. 桥梁建设

【题目背景】

一条宽阔的河流中矗立着若干高度各异的河柱，它们从河岸延伸至对岸，形成一条笔直的排列线。

【题目描述】

我们计划建造一座以河柱为支撑的桥梁，为此需要选取部分河柱，将它们的顶端连接成桥段。所选河柱集合必须包含首尾两柱。

建造第i与j号河柱间桥段的成本为（hi-hj）²（hi表示第i号河柱的高度），以避免桥段不均匀。

同时，所有非桥段河柱都需拆除，因为它们会阻碍河道通航。拆除第i号河柱的成本为wi，该成本甚至可能为负值——某些利益相关方愿意支付费用以清除特定河柱。所有高度hi和成本wi均为整数。

那么，连接首尾两柱的桥梁建设，其最低可能成本是多少？

【输入格式】

第一行包含柱子数量n。

第二行按顺序列出柱子高度hi，各柱高度之间以空格分隔。

第三行按相同顺序列出移除柱子的成本wi。

【输出格式】

输出建造桥梁的最低成本。注意该成本可能为负值。

【样例输入】

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

【样例输出】

17

【样例说明】

在此键入。

【数据规模与约定】

大样例

对于测试点1-5 ，有n<=1000

对于测试点6-10，最优解最多包含2个额外支柱（除首尾支柱外）且|wi| ≤ 20

对于 100% 的数据，有 2≤n≤10^5;  0≤hi,|wi| ≤10^6。

【来源】

在此键入。