今天是 3025 年 5 月 25 日。代尔夫特理工大学（TU Delft）的 EEMCS 大楼已经增建到了地面以上 $10^6$ 层！现在的楼层编号为 $0, 1, \dots, 10^6$，但依然只有四部电梯。此外，这些电梯发生了故障，目前处于关闭状态。作为大楼攀爬计划公司（Building Ascension Plans Company）的员工，你的任务是修复这些电梯。你首先需要订购一些配件，这些配件需要一个月的时间才能送达地面层。在收集齐配件后，你必须依次前往 $n$ 个楼层 $f_1, \dots, f_n$。在每个楼层 $f_i$，你必须更换某些配件，这需要花费 $t_i$ 秒。在更换完最后一个配件后，电梯就会被修复。

EEMCS 大楼，现在有一百万层高。

由于人们厌倦了攀爬数百万级的楼梯，楼梯早就被拆除了。因此，你必须乘坐电梯在楼层之间移动。你可以开启电梯，但一旦开启，就无法再将其关闭。一旦开启，电梯将在 $0$ 层和 $10^6$ 层之间无限循环上下移动。电梯的移动速度为每秒一层，且中途不会停靠，但你足够敏捷，可以在电梯运行过程中自由进出。

你确切地知道配件何时送达。在此期间，你可以决定何时开启每部电梯。这个开启时间决定了当配件送达时，每部电梯的初始状态。由于你有一个月的时间，你可以让电梯处于任何你想要的初始状态。修复电梯所需的最短时间是多少？

作为一个例子，考虑第一个样例输入。你可以让一部电梯在地面层开始向上运行，另一部电梯在 $750\,000$ 层开始向上运行。立即进入第一部电梯，你在 $600\,000$ 秒后到达 $600\,000$ 层。再过 $50\,000$ 秒，你完成了在 $600\,000$ 层的配件更换。与此同时，第二部电梯在 $250\,000$ 秒后到达顶层，并开始向下运行。此时，又过了 $400\,000$ 秒，这部电梯正好运行到 $600\,000$ 层且正在向下移动。你可以立即进入这部电梯，并在 $200\,000$ 秒后在 $400\,000$ 层离开。最后，经过 $150\,000$ 秒，你完成了在 $400\,000$ 层的配件更换，电梯全部修复完毕！总时间为 $600\,000 + 50\,000 + 200\,000 + 150\,000 = 1\,000\,000$ 秒。

输入格式

输入包含：

• 第一行包含一个整数 $n$ ($1 \le n \le 35$)，表示需要访问的楼层数。
• 第二行包含 $n$ 个整数 $f_1, \dots, f_n$（对每个 $i$ 满足 $0 \le f_i \le 10^6$），表示你必须依次访问的楼层编号。
• 第三行包含 $n$ 个整数 $t_1, \dots, t_n$（对每个 $i$ 满足 $1 \le t_i \le 10^9$），表示在每个楼层上更换配件所需的秒数。

输入保证相邻的两个楼层 $f_i, f_{i+1}$ 不相同，且 $f_1$ 不为零。

输出格式

输出在配件送达且你从地面层出发后，修复电梯所需的最短时间（以秒为单位）。

样例

输入样例 1

2
600000 400000
50000 150000

输出样例 1

1000000

输入样例 2

10
1 2 3 4 5 6 7 8 9 10
1 1 1 1 1 1 1 1 1 1

输出样例 2

4000012