该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

美术社要把一幅长卷封装起来。长卷被分成了 n 段，从左到右依次摆放。第 i 段长卷有两个属性：

• 长度 $a_i$；
• 纹样编号 $c_i$。

封装时，每次只能选择两段相邻、且已经封好的连续长卷，把它们合成一段更长的长卷。

如果本次合成后的长卷总长度为 L，且新长卷最左端纹样编号为 x，最右端纹样编号为 y，那么本次封装需要消耗：

L + |x - y|

经过若干次封装后，所有长卷会变成一整段。请你求出最少需要消耗多少。

输入格式

第一行一个整数 n。

第二行 n 个整数 $a_1, a_2, ..., a_n$。

第三行 n 个整数 $c_1, c_2, ..., c_n$。

输出格式

输出一个整数，表示最少封装消耗。

样例

输入

4
1 2 3 4
1 3 2 5

输出

26

数据范围

$1 <= n <= 350$ $1 <= a_i <= 10^4$ $1 <= c_i <= 10^9$

测试点设计