分数: 1200 点
问题陈述
想象一下在线游戏。最初,玩家位于位置 0 与 N 糖果在他手中,出口位于 位置 E。还有 N 游戏中的熊。的 i- 第熊位于 x_i。玩家的最大移动速度为 1 而熊根本不动。
当玩家给小熊糖果时,小熊会在之后提供一枚硬币 T 时间单位。更具体地说,如果 i第-只熊在某个时间得到了一颗糖果 t,它会在该时间的位置放一枚硬币 t+T。这个游戏的目的是给所有的小熊糖果,捡起所有的硬币,然后走到出口。请注意,只有当玩家处于与熊完全相同的位置时,玩家才能给熊糖果。此外,每只熊只能生产一次硬币。如果玩家在硬币被放下之后或恰好同时访问了硬币的位置,则玩家可以捡起硬币。硬币在被玩家收集之前不会消失。
Shik 是这个游戏的专家。他可以给熊糖果并立即捡起硬币。您将获得游戏的配置。请计算 Shik 收集所有硬币并到达出口所需的最短时间。
约束
- 1 \leq N \leq 100,000
- 1 \leq T, E \leq 10^9
- 0 < x_i < E
- x_i < x_{i+1} 为 1 \leq i < N
- 所有输入值均为整数。
部分分数
- 在测试用例中值得 600 点, N \leq 2,000.
输入
输入由标准输入按以下格式给出:
N E T x_1 x_2 ... x_N
输出
打印一个表示答案的整数。
示例输入 1
3 9 1 1 3 8
示例输出 1
12
最佳策略是在治疗完每只熊后等待硬币。总共花费的等待时间为 3 移动是 9。所以答案是 3 + 9 = 12.
示例输入 2
3 9 3 1 3 8
示例输出 2
16
示例输入 3
2 1000000000 1000000000 1 999999999
示例输出 3
2999999996