Description

你现在要建桥

一共有$n$根柱子，其中最左和最右的柱子是不能移动的

你现在要去除掉一些柱子来建桥，去除掉第$i$根的花费是$w_i$

在相邻两根柱子之间建路面要花费$(h_i-h_j)^2$，其中$h_i$是第$i$根柱子的高度

求建桥的最小花费

Input

第一行一个$n$

第二行$n$个数，表示是柱子的高度$h_i$

第三行$n$个数，表示是去除柱子的花费$w_i$

一个数，最小花费

3 8 7 1 6 6

0 -1 9 1 2 0

$2\leq n\leq 10^5$

$0\leq h_i\leq 10^6$

$0\leq |w_i|\leq 10^6$

本题使用subtask进行评测

subtask1(30pts): $n\leq 1000$

subtask2(30pts): 存在一组最优解仅保存除了最左最右以外的两根柱子，$w_i\leq 20$

subtask3(40pts): 无任何限制