AT_agc007_d [AGC007D] Shik and Game

[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/A

N/A

### 制約 - $ 1\ \leq\ N\ \leq\ 100,000 $ - $ 1\ \leq\ T,\ E\ \leq\ 10^9 $ - $ 0\