[AGC022D] Shopping

- 有 $n$ 个商场, 第 $i$ 个商场在数轴上的 $x_i$ 处, 你需要在第 $i$ 个商场花费连续的 $t_i$ 单位时间购物. - 现在有一趟火车会在 $0$ 到 $L$ 处往返, 行驶一单位距离要花费一单位时间. - 你从 $0$ 时刻起在 $0$ 处上车, 只有在商场, $0$ 处或 $L$ 处才能下车, 问最少花费多少单位时间能在每一个商场都购完物后回到 $0$ 处. - $n\leqslant 3\times 10^5, 0<x<L\leqslant 10^9$.

[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 $ $ L $ $ x_{1} $ $ x_{2} $ $ ... $ $ x_{N} $ $ t_{1} $ $ t_{2} $ $ ... $ $ t_{N} $

ユイが $ N $ 件すべてのショッピングセンターで買い物を済ませて帰宅するまでに必要な最短の時間を（秒単位で）出力せよ。

2 10
5 8
10 4

40

2 10
5 8
10 5

60

5 100
10 19 28 47 68
200 200 200 200 200

1200

8 1000000000
2018 123456 1719128 1929183 9129198 10100101 77777777 120182018
99999999 1000000000 1000000000 11291341 1 200 1 123812831

14000000000

### 制約 - $ 1\ \leq\ N\ \leq\ 300000 $ - $ 1\ \leq\ L\ \leq\ 10^{9} $ - $ 0\ <\ x_{1}\ <\ x_{2}\ <\ ...\ <\ x_{N}\ <\ L $ - $ 1\ \leq\ t_{i}\ \leq\ 10^{9} $ - 入力中のすべての値は整数である。 ### 部分点 - $ 1\ \leq\ N\ \leq\ 3000 $ を満たすデータセットに正解すると、$ 1000 $ 点が与えられる。 ### Sample Explanation 1 ユイが買い物を済ませる行程の例を示します。 - 列車で座標 $ 8 $ の駅まで移動する。時刻 $ 8 $ に座標 $ 8 $ に到着する。 - 座標 $ 8 $ のショッピングセンターで買い物をする。時刻 $ 12 $ に買い物が完了する。 - 時刻 $ 12 $ に電車が座標 $ 8 $ に到着する。負の方向に進んでいる電車に乗る。 - 時刻 $ 15 $ に座標 $ 5 $ に到着する。時刻 $ 25 $ に買い物が完了する。 - 時刻 $ 25 $ に電車が座標 $ 5 $ に到着する。正の方向に進んでいる電車に乗る。 - 時刻 $ 30 $ に座標 $ L\ =\ 10 $ に到着する。列車は直ちに反対方向に走り始める。 - 時刻 $ 40 $ に座標 $ 0 $ に到着し、行程を終了する。 ### Sample Explanation 4 オーバーフローにご注意。