题目描述

在一条直线上进行游戏。开始时，玩家位于坐标 $0$，手中有 $N$ 个糖果。坐标 $E$ 处有出口。除了玩家外，这条直线上还有 $N$ 只熊，第 $i$ 只熊静止在坐标 $x_i$。玩家可以以不超过 $1$ 的速度在直线上移动。

当玩家给熊 $1$ 个糖果时，熊会在 $T$ 单位时间后在原地吐出 $1$ 枚硬币。也就是说，如果在时刻 $t$ 给熊 $1$ 个糖果，则在时刻 $t+T$，该熊的位置会出现 $1$ 枚硬币。游戏的目标是给所有 $N$ 只熊都发放糖果，并收集所有 $N$ 枚硬币后从出口离开。要给熊糖果，玩家必须与熊处于同一位置。此外，每只熊最多只能被喂一次糖果。硬币在出现后，玩家只要到达硬币所在位置即可收集，且硬币不会在被收集前消失。

Shic 是这个游戏的高手。Shic 给熊糖果和捡硬币所需的时间极短，可以忽略不计。给定游戏的设定，请求出 Shic 收集所有硬币并从出口离开所需的最短时间。

输入格式

输入通过标准输入按以下格式给出。

$N$ $E$ $T$ $x_1$ $x_2$ $\ldots$ $x_N$

输出格式

输出 Shic 收集所有硬币并从出口离开所需的最短时间的整数。

样例 1

输入

3 9 1
1 3 8

输出

12

样例 2

输入

3 9 3
1 3 8

输出

16

样例 3

输入

2 1000000000 1000000000
1 999999999

输出

2999999996

说明/提示

限制条件

• $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$。

样例说明 1

一边朝出口前进，一边遇到熊就喂糖果，并在原地等待硬币出现是最优策略。此时，移动需要 $9$ 单位时间，$3$ 次等待共 $3$ 单位时间，总共需要 $12$ 单位时间。

由 ChatGPT 4.1 翻译