题目描述

有 n根柱子依次排列，每根柱子都有一个高度。第 i根柱子的高度为hi。 现在想要建造若干座桥，如果一座桥架在第i 根柱子和第j根柱子之间，那么需要 (hi-hj)^2的代价。 在造桥前，所有用不到的柱子都会被拆除，因为他们会干扰造桥进程。第 i 根柱子被拆除的代价为wi，注意 wi不一定非负，因为可能政府希望拆除某些柱子。 现在政府想要知道，通过桥梁把第 1 根柱子和第n 根柱子连接的最小代价。注意桥梁不能在端点以外的任何地方相交。

输入格式

第一行一个正整数n。 第二行n 个空格隔开的整数，依次表示 h1,h2,...,hn。 第三行n个空格隔开的整数，依次表示 w1,w2,...,wn。

输出格式

输出一行一个整数表示最小代价，注意最小代价不一定是正数。

样例

输入

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

输出

17

数据范围与提示

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

• 子任务 1（30%）：有 n<=1000；
• 子任务 2（30%）：有 |wi|<=20，保证存在一种最优方案，除了头尾两根柱子外，最多只保留两根柱子；
• 子任务 3（40%）：无特殊限制。