AT_agc022_d [AGC022D] Shopping

[problemUrl]: https://atcoder.jp/contests/agc022/tasks/agc022_d ユイは買い物好きです。ユイはヤマボシ市に住んでいて、この市では鉄道が運行しています。ヤマボシ市はとても長い数直線としてモデル化することができ、ユイの家は座標 $ 0 $ にあります。 ヤマボシ市には $ N $ 件のショッピングセンターがあり、それぞれ座標 $ x_{1},\ x_{2},\ ...,\ x_{N} $ にあります。鉄道の駅は $ N\ +\ 2 $ 駅あり、座標 $ 0 $ に一駅、座標 $ L $ に一駅、そして各ショッピングセンターに一駅ずつあります。 時刻 $ 0 $ に、鉄道列車が座標 $ 0 $ から正の方向に出発します。列車は毎秒 $ 1 $ 単位距離という一定の速さで移動します。時刻 $ L $ に、列車は終着駅、すなわち座標 $ L $ の駅に到着します。その直後に、列車は反対の方向に同じ速さで走り始めます。時刻 $ 2L $ に、列車は座標 $ 0 $ の駅に到着し、再び反対の方向に走り始めます。この行程が永遠に繰り返されます。 列車がユイのいる駅に到着したとき、ユイは直ちに列車に乗ったり降りたりすることができます。時刻 $ 0 $ には、ユイは座標 $ 0 $ の駅にいます。 ユイは $ N $ 件すべてのショッピングセンターに買い物に行きたいです。順番はなんでもよく、買い物が終わったら帰りたいです。座標 $ x_{i} $ のセンターでの買い物には $ t_{i} $ 秒がかかります。**あるセンターで買い物を始めたら、次のセンターに行く前にそこでの買い物を完了しなければなりません。** センターのある駅に到着したら直ちに買い物を始めることができ、買い物が終わったら直ちに電車に乗ることができます。 ユイは、買い物にかかる時間を最短にしたいです。最短で何秒で買い物を済ませられるか、ユイが判断するのを手伝ってくれませんか？

N/A

N/A

### 制約 - $ 1\ \leq\ N\ \leq\ 300000 $ - $ 1\ \leq\ L\ \leq\ 10^{9} $ - $ 0\