AT_agc022_d.[AGC022D] Shopping

Yui 很喜欢购物。Yui 住在 Yamaboshi 市，这个城市有铁路运行。Yamaboshi 市可以被建模为一条非常长的数轴，Yui 的家在坐标 $0$。

Yamaboshi 市有 $N$ 个购物中心，分别位于坐标 $x_{1},\ x_{2},\ ...,\ x_{N}$。铁路共有 $N+2$ 个车站，分别在坐标 $0$、坐标 $L$ 以及每个购物中心的位置各有一个车站。

在时刻 $0$，列车从坐标 $0$ 的车站出发，向正方向行驶。列车以每秒 $1$ 单位距离的恒定速度移动。在时刻 $L$，列车到达终点站（即坐标 $L$ 的车站）。到达后，列车立即以相同速度反向行驶。在时刻 $2L$，列车回到坐标 $0$ 的车站，并再次反向行驶。这个过程会无限循环。

每当列车到达 Yui 所在的车站时，Yui 可以立刻上下车。在时刻 $0$，Yui 在坐标 $0$ 的车站。

Yui 想要去所有 $N$ 个购物中心购物，顺序不限，购物结束后还要回家。在坐标 $x_{i}$ 的购物中心购物需要 $t_{i}$ 秒。在某个购物中心开始购物后，必须在前往下一个购物中心之前完成该处的购物。 到达购物中心所在的车站后可以立刻开始购物，购物结束后可以立刻乘车。

Yui 想让购物所需的总时间最短。请帮她判断，最短需要多少秒才能完成所有购物并回家？

输入从标准输入读取，格式如下：

$N$ $L$ $x_{1}$ $x_{2}$ $...$ $x_{N}$ $t_{1}$ $t_{2}$ $...$ $t_{N}$

输出 Yui 完成所有 $N$ 个购物中心购物并回家所需的最短时间（以秒为单位）。

限制

• $1 \leq N \leq 300000$
• $1 \leq L \leq 10^{9}$
• $0 < x_{1} < x_{2} < ... < x_{N} < L$
• $1 \leq t_{i} \leq 10^{9}$
• 输入中的所有数值均为整数。

部分得分

• 若能正确解决 $1 \leq N \leq 3000$ 的数据集，可获得 $1000$ 分。

样例解释 1

以下是 Yui 完成购物的一种行程示例：

• 乘坐列车前往坐标 $8$ 的车站。时刻 $8$ 到达坐标 $8$。
• 在坐标 $8$ 的购物中心购物。时刻 $12$ 完成购物。
• 时刻 $12$，列车到达坐标 $8$，乘坐反方向的列车。
• 时刻 $15$ 到达坐标 $5$。时刻 $25$ 完成购物。
• 时刻 $25$，列车到达坐标 $5$，乘坐正方向的列车。
• 时刻 $30$ 到达坐标 $L=10$，列车立即反向行驶。
• 时刻 $40$ 回到坐标 $0$，行程结束。

样例解释 4

请注意防止溢出。

由 ChatGPT 4.1 翻译