题目背景

3025 年 5 月 25 日，代尔夫特理工大学 EEMCS 大楼已经扩建到地面以上 $10^6$ 层，楼层编号为 $0,1,\ldots,10^6$，但整栋楼仍然只有四部电梯。

你需要维修这些电梯。维修零件会在一个月后送达地面层；零件到达后，你从第 $0$ 层出发，并必须按给定顺序访问若干楼层，在每个楼层完成相应维修。

题目描述

四部电梯初始均处于关闭状态。

一旦开启某部电梯，就不能再将其关闭。开启后，它会以每秒一层的速度，在第 $0$ 层和第 $10^6$ 层之间不停往返：

• 到达顶层后立即向下运行；
• 到达地面层后立即向上运行；
• 电梯不会停靠，但你可以瞬间进入或离开电梯。

你提前知道零件到达的准确时间。在等待的一个月内，你可以自行决定每部电梯何时启动，因此当零件到达时，可以使四部电梯处于任意希望的初始运行相位。

零件到达后，你位于第 $0$ 层，需要依次访问楼层

到达第 $i$ 个楼层 $f_i$ 后，需要花费 $t_i$ 秒更换零件。在维修期间，所有电梯仍会继续运动。

求完成全部维修所需的最短时间。

输入格式

第一行包含一个整数 $n$（$1\le n\le 35$），表示需要访问的楼层数量。

第二行包含 $n$ 个整数：

其中 $0\le f_i\le 10^6$，表示依次需要访问的楼层。

第三行包含 $n$ 个整数：

其中 $1\le t_i\le 10^9$，表示在第 $i$ 个楼层维修所需的秒数。

保证：

• 任意相邻的两个目标楼层不同，即 $f_i\ne f_{i+1}$；
• $f_1\ne 0$。

输出格式

输出一个整数，表示零件到达后，从地面层开始直至完成所有维修所需的最短秒数。

样例 1

输入

2
600000 400000
50000 150000

输出

1000000

样例说明

可以让一部电梯在时刻 $0$ 位于地面层并向上运行，另一部电梯位于第 $750000$ 层并向上运行。

• 乘第一部电梯 $600000$ 秒到达第 $600000$ 层；
• 维修 $50000$ 秒；
• 此时第二部电梯恰好到达第 $600000$ 层并向下运行；
• 再乘坐 $200000$ 秒到达第 $400000$ 层；
• 维修 $150000$ 秒。

总时间为：

样例 2

输入

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

输出

4000012