AdditionalFile4933.zip

#4933. 「POI2014 R3」装货 Freight

标签: 传统 | 时间限制: 2000 ms | 内存限制: 64 MiB |

题目描述

题目译自 XXI Olimpiada Informatyczna — III etap Załadunek

上字节镇和下字节镇的火车站由单条铁轨连接。火车单程耗时 $s$ 分钟，且发车间隔不得少于 $1$ 分钟。若铁轨上有多个火车，须同向行驶。

已知 $n$ 列火车将抵达上字节镇站，抵达时间已定。每列火车需前往下字节镇站装货后返回上字节镇站，装货时间可忽略。请你计算最后一列火车返回上字节镇站的最短时间。

输入格式

输入第一行包含两个整数 $n, s$ $(1 \leq n \leq 1000000, 1 \leq s \leq 10^9)$，分别表示火车数量和单程耗时（分钟）。

第二行包含 $n$ 个整数 $t_1, t_2, \ldots, t_n$ $(0 \leq t_1 \leq t_2 \leq \ldots \leq t_n \leq 10^9)$，表示各火车抵达上字节镇站的时间（分钟）。

输出格式

输出一行，一个整数，表示所有火车返回上字节镇站的最短时间（分钟）。

样例

输入

3 4
1 8 11

输出

20

为达到最优时间，火车可在上字节镇站的时刻 $1, 9, 11$ 发车，在下字节镇站的时刻 $5, 15, 16$ 返回，最终耗时 $20$ 分钟。

附加样例

1. $n=7, s=10$，简单正确性测试，前两列火车一起发车，后五列一起发车；
2. $n=100, s=5$，火车每 $10$ 分钟抵达一列，每列可完成全程后再来下一列；
3. $n=1000, s=3$，火车每分钟抵达，先全部依次发往一侧，再全部返回。

数据范围与提示

对于 $25\%$ 的数据，$n \leq 400$。
对于 $50\%$ 的数据，$n \leq 5000$。