题目描述

如下图所示，沿直线排列的道路上，从左到右依次编号为 $1$ 到 $N$ 的 $N$ 户人家。第 $i$ 户人家的位置为 $X_i$（$X_i > 0$）。

一家快递公司打算使用一辆卡车沿这些人家路线访问，回收各家要退回的物品。卡车从快递公司所在的位置 $0$ 出发，出发时间为时刻 $0$。第 $i$ 户人家会在时刻 $T_i$ 将退货物品摆出。卡车以速度 $1$ 移动，因此移动距离为 $d$ 时，需要花费 $d$ 单位时间。卡车也可以原地等待，不必一直行驶。

卡车一旦经过某户人家的位置，就可以瞬间回收退货物品。也就是说，回收物品所需时间为 $0$。因此，只要卡车在时刻 $T_i$ 或之后经过位置 $X_i$，就能成功回收第 $i$ 户人家的退货物品。

现在给定各户人家在直线道路上的位置和其放出退货物品的时刻，请你编写程序，计算卡车完成所有退货物品回收，并返回快递公司所需的最短时间。

输入格式

第一行输入一个整数 $N$，表示需要回收退货物品的人家数量。
第二行输入 $N$ 个整数，表示各户人家的位置 $X_1, X_2, \dots, X_N$，以空格分隔。
第三行输入 $N$ 个整数，表示各户人家将退货物品摆出的时间 $T_1, T_2, \dots, T_N$，以空格分隔。

输出格式

输出一个整数，表示卡车回收所有物品并返回快递公司所需的最短时间。

4
2 5 7 10
20 4 16 11

23

3
1 2 3
3 2 1

6

提示

样例 1 解释

以下提供一种可以在 $23$ 的单位时间内回收所有货物的方式。

• 从起点 $0$ 前进到位置 $5$，回收货物 $2$。已耗时：$5$
• 从位置 $5$ 前进到位置 $10$，回收货物 $4$。已耗时：$5+5=10$
• 从位置 $10$ 回退到位置 $7$，回收货物 $3$。已耗时：$5+5+3=13$，由于该货物在时刻 $16$ 才会摆出，因此需要额外等待时刻 $3$，因此耗时为：$5+5+3+3=16$。
• 从位置 $7$ 回退到位置 $2$，回收货物 $1$。已耗时：$5+5+3+3+5=21$
• 回到起点，因此总耗时为 $23$。

可以证明不存在更短的时间使得回收完所有货物。

数据范围

$1 \leq N \leq 3000$，$1 \leq X_1 < X_2 < \cdots < X_N \leq 10^8$，$0 \leq T_i \leq 10^8$。

• 子任务 1 （10 分）$N = 2$
• 子任务 2 （15 分）$N \leq 9$
• 子任务 3 （5 分）对所有 $1 \leq i \leq N$，$T_i = 0$
• 子任务 4 （25 分）对所有 $2 \leq i \leq N$，都有 $T_{i-1} \leq T_i$
• 子任务 5 （45 分）无附加限制条件