P12643 [KOI 2024 Round 1] 回收退货

试题来源：。中文翻译做了少量本土化修改。 按照[署名—非商业性使用—相同方式共享 4.0 协议国际版](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh-hans)进行授权。

如下图所示，沿直线排列的道路上，从左到右依次编号为 $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$，以空格分隔。

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

**约束条件** - 所有给定的数均为整数。 - $1 \leq N \leq 3000$ - $1 \leq X_1 < X_2 < \cdots < X_N \leq 10^8$ - $0 \leq T_i \leq 10^8 \quad (1 \leq i \leq N)$ **子问题** 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 分）无附加限制条件 翻译由 ChatGPT-4o 完成