D - Shopping Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 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 件すべてのショッピングセンターで買い物を済ませて帰宅するまでに必要な最短の時間を（秒単位で）出力せよ。

入力例 1

2 10
5 8
10 4

出力例 1

40

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

  • 列車で座標 8 の駅まで移動する。時刻 8 に座標 8 に到着する。

  • 座標 8 のショッピングセンターで買い物をする。時刻 12 に買い物が完了する。

  • 時刻 12 に電車が座標 8 に到着する。負の方向に進んでいる電車に乗る。

  • 時刻 15 に座標 5 に到着する。時刻 25 に買い物が完了する。

  • 時刻 25 に電車が座標 5 に到着する。正の方向に進んでいる電車に乗る。

  • 時刻 30 に座標 L = 10 に到着する。列車は直ちに反対方向に走り始める。

  • 時刻 40 に座標 0 に到着し、行程を終了する。

入力例 2

2 10
5 8
10 5

出力例 2

60

入力例 3

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

出力例 3

1200

入力例 4

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

出力例 4

14000000000

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

Score : 1600 points

Problem Statement

Yui loves shopping. She lives in Yamaboshi City and there is a train service in the city. The city can be modelled as a very long number line. Yui's house is at coordinate 0.

There are N shopping centres in the city, located at coordinates x_{1}, x_{2}, ..., x_{N} respectively. There are N + 2 train stations, one located at coordinate 0, one located at coordinate L, and one located at each shopping centre.

At time 0, the train departs from position 0 to the positive direction. The train travels at a constant speed of 1 unit per second. At time L, the train will reach the last station, the station at coordinate L. The train immediately moves in the opposite direction at the same speed. At time 2L, the train will reach the station at coordinate 0 and it immediately moves in the opposite direction again. The process repeats indefinitely.

When the train arrives at a station where Yui is located, Yui can board or leave the train immediately. At time 0, Yui is at the station at coordinate 0.

Yui wants to go shopping in all N shopping centres, in any order, and return home after she finishes her shopping. She needs to shop for t_{i} seconds in the shopping centre at coordinate x_{i}. She must finish her shopping in one shopping centre before moving to the next shopping centre. Yui can immediately start shopping when she reaches a station with a shopping centre and she can immediately board the train when she finishes shopping.

Yui wants to spend the minimum amount of time to finish her shopping. Can you help her determine the minimum number of seconds required to complete her shopping?

Constraints

  • 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}
  • All values in the input are integers.

Partial Score

  • 1000 points will be awarded for passing the testset satisfying 1 \leq N \leq 3000.

Input

Input is given from Standard Input in the following format:

N L
x_{1} x_{2} ... x_{N}
t_{1} t_{2} ... t_{N}

Output

Print the minimum time (in seconds) required for Yui to finish shopping at all N shopping centres and return home.

Sample Input 1

2 10
5 8
10 4

Sample Output 1

40

Here's one possible way for Yui to finish her shopping :

  • Travel to the station at coordinate 8 with the train. She arrives at coordinate 8 at time 8.

  • Shop in the shopping centre at coordinate 8. She finishes her shopping at time 12.

  • The train arrives at coordinate 8 at time 12. She boards the train which is currently moving in the negative direction.

  • She arrives at coordinate 5 at time 15. She finishes her shopping at time 25.

  • The train arrives at coordinate 5 at time 25. She boards the train which is currently moving in the positive direction.

  • She arrives at coordinate L = 10 at time 30. The train starts moving in the negative direction immediately.

  • She arrives at coordinate 0 at time 40, ending the trip.

Sample Input 2

2 10
5 8
10 5

Sample Output 2

60

Sample Input 3

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

Sample Output 3

1200

Sample Input 4

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

Sample Output 4

14000000000

Beware of overflow issues.