[AGC007D] Shik and Game

Shik 君在玩一个游戏。 初始时他在数轴的 $0$ 位置，出口在 $E$ 位置，并且数轴上还有 $n$ 只小熊，第 $i$ 只小熊在 $x_i$ 位置。 Shik 君拿着 $n$ 块糖果出发，每走一个单位长度要花费一秒。到一个小熊的位置时，他可以送给这个小熊一块糖果，这个过程不花时间。小熊收到糖果后，$T$ 秒以后会在它所在的位置产生一个金币。 Shik 君想知道，他从出发到收集了所有金币抵达出口，最少要花费多长时间。

[problemUrl]: https://atcoder.jp/contests/agc007/tasks/agc007_d 一直線上でゲームを行います。はじめプレイヤーは座標 $ 0 $ におり、キャンディを $ N $ 個持っています。座標 $ E $ に出口があります。プレイヤーの他に、この直線上には $ N $ 匹のクマがおり、$ i $ 匹目のクマは座標 $ x_i $ で静止しています。プレイヤーは直線上を $ 1 $ 以下の速度で動くことができます。 プレイヤーがクマにキャンディを $ 1 $ 個与えると、クマは $ T $ 単位時間後に $ 1 $ 枚のコインをその場に吐き出します。すなわち、時刻 $ t $ にクマにキャンディを $ 1 $ 個与えると、時刻 $ t+T $ にそのクマの位置に $ 1 $ 枚のコインが出現します。このゲームの目的は、$ N $ 匹すべてのクマにキャンディを与え、$ N $ 枚のコインをすべて回収して出口から脱出することです。クマにキャンディを与えるためには、プレイヤーはクマと同じ位置にいなければなりません。また、$ 1 $ 匹のクマに $ 2 $ 回以上キャンディを与えることはできません。コインは、出現した瞬間以降にプレイヤーがコインと同じ位置にいれば回収できます。プレイヤーが回収する前にコインが消滅することはありません。 シックはこのゲームの達人です。シックがクマにキャンディを与えたり、コインを拾うのに必要な時間は極めて短く、無視することができます。ゲームの設定が与えられるので、シックがすべてのコインを集めて出口から脱出するまでに必要な最短時間を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ E $ $ T $ $ x_1 $ $ x_2 $ $ ... $ $ x_N $

シックがすべてのコインを集めて出口から脱出するまでに必要な最短時間を表す整数を出力せよ。

3 9 1
1 3 8

12

3 9 3
1 3 8

16

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 $ が成り立つ。 ### Sample Explanation 1 出口に向かいながら、クマに会うたびにキャンディを与え、その場でコインが出るのを待つのが最適です。このとき、移動に $ 9 $ 単位時間、$ 3 $ 回の待機に $ 3 $ 単位時間、合計で $ 12 $ 単位時間を要します。