You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

维修零件

题目背景

题目描述

小明在汽车厂打螺丝，这天汽车厂回收了$n$个损坏的零件，小明所在的车间负责维修这些零件。

车间维修零件的工序是这样的：维修小组负责修好这些零件，修好之后这些零件被放到传送带上，传送到小明的位置，然后小明负责检查这些零件是否已经维修好，再放到另一条传送带上将零件运送回去。根据零件的损坏程度不同，第$i$个零件需要$t_i$的时间来修好，也就是说这个零件最早在$t_i$时刻能从维修一侧传递至小明一侧。零件从传送带一端到另一端所用的时长为$s$单位时间，每个单位时间两边都最多往传送带上放一个零件，即任何两个零件放上传送带的间隔都至少要1个单位时间。

然而今天车间坏了一条传送带，因此只有一条传送带能工作，就是说小明需要调节传送带的方向来完成这个检修程序。因此，可能会出现小明这边检修完若干个零件之后再一次性依次把这些零件传送回去的情况。小明只能在传送带上没有零件的情况下才能调整传送带的方向，调节传送带方向和检测零件的时间都忽略不计。

小明想早点下班，所以他向你求助，在知道$n$，$s$，$t_i$的情况下，能否求出最后一个零件返回另一边的最早时刻？

输入格式

第一行两个正整数$n$和$s$。

第二行$n$个非负整数$t_i$。

输出格式

一个正整数表示答案。

样例 #1

样例输入 #1

3 4
1 7 12

样例输出 #1

21

提示

样例解释1：

第1个零件在时刻1从维修端出发，时刻5到达小明处，小明在时刻5反转传送带方向，让第1个零件在时刻9返回维修端，此时第2个零件已经修好。

此时小明反转传送带方向，让第2个零件在时刻9从维修端出发，第3个零件在时刻12从维修端出发，然后第2个零件在时刻13到达小明处，第3个零件在时刻16到达小明处，小明在时刻16反转传送带方向并放上第2个零件，在时刻17放上第3个零件，那么第2个零件在时刻20返回维修端，第3个零件在时刻21返回维修端，工作结束。

数据范围 对$40\%$的数据，$1≤n≤5000,1≤s,t_i≤10000$。

对$100\%$的数据，$1≤n≤10^6,1≤s,t_i≤10^9$，数据保证$t_i$单调不减。