题目描述

#nck { width: 30px; height: auto; }

想象一个在一条线上进行的游戏。一开始，玩家位于位置 $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$
• 对于 $1 \leq i < N$，有 $x_i < x_{i+1}$。
• 所有输入值均为整数。

分数细节

• 在价值为 $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