Upper Bytown 和 Lower Bytown 的火车站之间由一条单轨铁路连接。火车在两站之间往返行驶均需 $s$ 分钟。然而，从同一车站出发的火车之间必须至少间隔一分钟。此外，在任何时刻，轨道上所有的火车都必须朝同一个方向行驶。

根据我们掌握的时刻表，有 $n$ 列货运列车计划经过 Upper Bytown 前往 Lower Bytown。它们需要在 Lower Bytown 装载货物，然后返回 Upper Bytown。为简化起见，我们假设火车装载货物的时间可以忽略不计。

我们需要确定最后一列火车返回 Upper Bytown 的最小可能时间。

输入格式

输入的第一行包含两个整数 $n$ 和 $s$ ($1 \le n \le 1\,000\,000$, $1 \le s \le 10^{9}$)，分别表示列车数量和单程行驶时间，中间用空格分隔。第二行包含 $n$ 个整数 $t_{1}, t_{2}, \dots, t_{n}$ ($0 \le t_{1} \le t_{2} \le \dots \le t_{n} \le 10^{9}$)，表示各列车到达 Upper Bytown 车站的时间，中间用空格分隔。

在总分 $50\%$ 的测试点中，$n \le 5\,000$。此外，在其中占总分 $25\%$ 的子任务中，额外满足 $n \le 400$。

输出格式

程序应输出一行，包含一个整数：最后一列火车返回 Upper Bytown 的最小可能时间。

样例

输入 1

3 4
1 8 11

输出 1

20

说明 1

为了达到最小时间，火车可以分别在时刻 1、9 和 11 从 Upper Bytown 出发，并在时刻 5、15 和 16 从 Lower Bytown 返回。