题目描述

一栋大楼现在有从 0 到 \(10^6\) 的楼层，一共四部电梯，但它们都坏了，而且当前处于关闭状态。

你需要在零层等待零件送到。零件到达后，你必须按顺序访问 \(n\) 个楼层 \(f_1, f_2, \dots, f_n\)。在第 \(i\) 个楼层上，你需要停留 \(t_i\) 秒更换零件。完成最后一次更换后，所有电梯就修好了。

楼梯已经被拆掉，因此你只能依靠电梯移动。电梯有如下性质：

• 你可以在任意时刻打开任意一部电梯；
• 一旦打开，就再也不能关闭；
• 打开后，电梯会在楼层 0 和 \(10^6\) 之间持续往返运动；
• 电梯速度恒为每秒 1 层，中途不停；
• 你可以在电梯经过某层时立刻上下电梯，不耗时。

因为零件要一个月后才送到，所以在这一个月中，你可以自由安排四部电梯的开启时刻，从而让它们在零件到达的那一刻处于任意你想要的初始位置与运动方向。

你在零件到达时从 0 楼 出发。请问最早多久可以完成所有维修？

输入格式

第一行一个整数 \(n\)，表示需要访问的楼层数量：

• \(1 \le n \le 35\)

第二行 \(n\) 个整数 \(f_1, f_2, \dots, f_n\)，表示必须依次访问的楼层：

• \(0 \le f_i \le 10^6\)

第三行 \(n\) 个整数 \(t_1, t_2, \dots, t_n\)，表示在对应楼层上需要停留的秒数：

• \(1 \le t_i \le 10^9\)

额外保证：

• 任意相邻两个楼层 \(f_i, f_{i+1}\) 不相等；
• \(f_1 \ne 0\)。

输出格式

输出一个整数，表示从你在 0 楼开始，到修好所有电梯所需的最短时间（单位：秒）。

样例输入 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