配点 : $1200$ 点

問題文

一直線上でゲームを行います。はじめプレイヤーは座標 $0$ におり、キャンディを $N$ 個持っています。座標 $E$ に出口があります。プレイヤーの他に、この直線上には $N$ 匹のクマがおり、$i$ 匹目のクマは座標 $x_i$ で静止しています。プレイヤーは直線上を $1$ 以下の速度で動くことができます。

プレイヤーがクマにキャンディを $1$ 個与えると、クマは $T$ 単位時間後に $1$ 枚のコインをその場に吐き出します。すなわち、時刻 $t$ にクマにキャンディを $1$ 個与えると、時刻 $t+T$ にそのクマの位置に $1$ 枚のコインが出現します。このゲームの目的は、$N$ 匹すべてのクマにキャンディを与え、$N$ 枚のコインをすべて回収して出口から脱出することです。クマにキャンディを与えるためには、プレイヤーはクマと同じ位置にいなければなりません。また、$1$ 匹のクマに $2$ 回以上キャンディを与えることはできません。コインは、出現した瞬間以降にプレイヤーがコインと同じ位置にいれば回収できます。プレイヤーが回収する前にコインが消滅することはありません。

シックはこのゲームの達人です。シックがクマにキャンディを与えたり、コインを拾うのに必要な時間は極めて短く、無視することができます。ゲームの設定が与えられるので、シックがすべてのコインを集めて出口から脱出するまでに必要な最短時間を求めてください。

制約

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

出力

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

3 9 1
1 3 8

12

出口に向かいながら、クマに会うたびにキャンディを与え、その場でコインが出るのを待つのが最適です。このとき、移動に $9$ 単位時間、$3$ 回の待機に $3$ 単位時間、合計で $12$ 単位時間を要します。

3 9 3
1 3 8

16

2 1000000000 1000000000
1 999999999

2999999996