分数: 1600 点
问题陈述
Yui 喜欢购物。她住在山星市,市内有火车服务。城市可以建模为一条很长的数轴。 Yui的房子在坐标上 0.
有 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 购物中心,按任意顺序,购物完毕后返回家。她需要购物 t_{i} 坐标购物中心秒数 x_{i}. 她必须在一个购物中心完成购物,然后才能前往下一个购物中心。 Yui 到达有购物中心的车站时可以立即开始购物,购物完成后可以立即登上火车。
Yui 想花最少的时间完成她的购物。你能帮助她确定完成购物所需的最短秒数吗?
约束
- 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}
- 输入中的所有值都是整数。
部分分数
- 1000 通过满足以下条件的测试集将获得积分 1 \leq N \leq 3000.
输入
输入由标准输入按以下格式给出:
N L
x_{1} x_{2} ... x_{N}
t_{1} t_{2} ... t_{N}
输出
打印 Yui 完成购物所需的最短时间(以秒为单位) N 购物中心并返回家。
示例输入 1
2 10 5 8 10 4
示例输出 1
40
这是 Yui 完成购物的一种可能方式:
-
前往坐标处的车站 8 随火车。她到达坐标 8 时间 8.
-
在坐标购物中心购物 8。她按时完成购物 12.
-
火车到达坐标 8 时间 12。她登上了目前正向负方向行驶的火车。
-
她到达坐标 5 时间 15。她按时完成购物 25.
-
火车到达坐标 5 时间 25。她登上了目前正向行驶的火车。
-
她到达坐标 L = 10 时间 30。火车立即开始向负方向行驶。
-
她到达坐标 0 时间 40,结束行程。
示例输入 2
2 10 5 8 10 5
示例输出 2
60
示例输入 3
5 100 10 19 28 47 68 200 200 200 200 200
示例输出 3
1200
示例输入 4
8 1000000000 2018 123456 1719128 1929183 9129198 10100101 77777777 120182018 99999999 1000000000 1000000000 11291341 1 200 1 123812831
示例输出 4
14000000000
注意溢出问题。