配点 : $1600$ 点

問題文

ユイは買い物好きです。ユイはヤマボシ市に住んでいて、この市では鉄道が運行しています。ヤマボシ市はとても長い数直線としてモデル化することができ、ユイの家は座標 $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}$ 秒がかかります。あるセンターで買い物を始めたら、次のセンターに行く前にそこでの買い物を完了しなければなりません。 センターのある駅に到着したら直ちに買い物を始めることができ、買い物が終わったら直ちに電車に乗ることができます。

ユイは、買い物にかかる時間を最短にしたいです。最短で何秒で買い物を済ませられるか、ユイが判断するのを手伝ってくれませんか？

制約

• $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$ 点が与えられる。

入力

入力は標準入力から以下の形式で与えられる。

$N$ $L$

$x_{1}$ $x_{2}$ $...$ $x_{N}$

$t_{1}$ $t_{2}$ $...$ $t_{N}$

出力

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

2 10
5 8
10 4

40

ユイが買い物を済ませる行程の例を示します。

• 列車で座標 $8$ の駅まで移動する。時刻 $8$ に座標 $8$ に到着する。
• 座標 $8$ のショッピングセンターで買い物をする。時刻 $12$ に買い物が完了する。
• 時刻 $12$ に電車が座標 $8$ に到着する。負の方向に進んでいる電車に乗る。
• 時刻 $15$ に座標 $5$ に到着する。時刻 $25$ に買い物が完了する。
• 時刻 $25$ に電車が座標 $5$ に到着する。正の方向に進んでいる電車に乗る。
• 時刻 $30$ に座標 $L = 10$ に到着する。列車は直ちに反対方向に走り始める。
• 時刻 $40$ に座標 $0$ に到着し、行程を終了する。

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

オーバーフローにご注意。