Franklinは、最新の流行のタイムアクションビデオゲームをプレイしており、ボスラッシュに直面しています。これは、生き残るために $N$ 体のモンスター（ボス）を倒さなければならない過酷な試練です。彼の唯一の能力である「パリィ」は非常に強力ですが、使用するのが非常に困難です。

各ボスは $d$ 秒ごとに1回Franklinを攻撃します。ただし、各ボスには攻撃を開始するまでの独自の開始遅延があるため、ボスの攻撃は時間的にずれています。具体的には、$i$ 番目のボスの開始遅延を $f_i$ とすると、そのボスは $f_i, f_i + d, f_i + 2d, \dots$ 秒に攻撃を行います。

身を守るため、Franklinは攻撃が発生したその瞬間にパリィを行うことができ、それによってボスを即座に倒し、その後のすべての攻撃を終了させることができます。Franklinは一度に1つの攻撃しかパリィできません。もし複数のボスが同時に攻撃してきた場合、そのうち最大1つしかパリィできません。

さらに、攻撃をパリィした後、Franklinは息切れ状態となり、次の $w$ 秒間はパリィを行うことができません。形式的には、Franklinが時刻 $t$ に攻撃をパリィした場合、次にパリィを行える最も早い時刻は $t + w$ です。

Franklinは体力が十分にあるため、ボスからの攻撃については心配していませんが、できるだけ早く戦いを終わらせたいと考えています。Franklinが最適にパリィを行う場合、すべての $N$ 体のボスを倒すのにかかる最小の時間を計算してください。

入力

入力の最初の行には、3つのスペース区切りの整数 $N$ ($1 \le N \le 3 \cdot 10^5$)、$w$ ($1 \le w \le 10^9$)、$d$ ($1 \le d \le 10^9$) が含まれます。ここで、$N$ はボスの数、$w$ はFranklinがパリィした後に次のパリィまで待機しなければならない秒数、$d$ は同じボスによる攻撃の間隔（秒）です。

次の行には、$N$ 個のスペース区切りの整数 $f_i$ ($0 \le f_i < d$) が含まれており、各ボスの開始遅延（秒）を表します。

出力

Franklinが最適にパリィを行う場合、すべての $N$ 体のボスを倒すのにかかる秒数を出力してください。

注記

入出力例 1 の説明

最初のボスは2秒にFranklinを攻撃します。Franklinはその攻撃をパリィすることもできますが、時を待って3秒に2番目のボスの攻撃をパリィすることを選択します。彼は息切れ状態となり、7秒前までは再びパリィを行うことができません。

3番目のボスは8秒に攻撃し、Franklinはその攻撃をパリィします。彼は再び息切れ状態となり、12秒までパリィできません。これはちょうど最初のボスの2回目の攻撃をパリィするタイミングであり、これで戦いが終了します。

入出力例

入力 1

3 4 10
2 3 8

出力 1

12

入力 2

3 4 10
2 3 9

出力 2

13