← 返回题目列表

AtCoder · agc022_d

D. 购物

中文机器翻译题面 查看原题

分数: 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

注意溢出问题。