No.808 Kaiten Sushi?

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 43
作問者 : sinsincoscossinsincoscos / テスター : noshi91noshi91
10 ProblemId : 2775 / 出題時の順位表
問題文最終更新日: 2019-03-22 12:57:25

問題文

 umgくんは今日から近所に開店したというKaiten Sushiに来ました。umgくんは一番乗りだったようで,他に客はいません。Kaiten Sushiは円形のカウンターがあり,その周の長さは$L$メートルです。 umgくんは入店後,席に案内されました。店内のカウンターには$N$貫の寿司と$N$杯のお茶があります。寿司$i$はumgくんから見て時計回りに$x_i$メートルの位置にあり, お茶$j$は$y_j$メートルの位置にあります。同じ位置に寿司やお茶が2つ以上存在することはありません。

 umgくんが「スタート」とコールすると,umgくんの座っている席が,カウンターに沿って時計回りに秒速$1$メートルで動き出します。umgくんは,寿司のある位置に来たらその寿司を取って食べることができます。取らなくても構いません。 umgくんは飲み込むのが遅いので,寿司を$1$貫食べた後は,次の寿司を食べる前にお茶を$1$杯飲む必要があります。お茶も寿司と同様,お茶のある位置に来たときに初めて,そのお茶を飲むことができますが,飲まなくても構いません。 寿司もお茶も,一度消費したら新たに追加されることはありません。円形のカウンターなので,umgくんが満足するまで席はカウンターに沿って回り続けます。

 umg君は$N$貫の寿司と$N$杯のお茶をすべて消費し,$N$杯目のお茶を飲んだら会計の後即座に店を出ます。umgくんが適切に寿司とお茶を消費したとき,移動を開始してから退店するまでの最短の時間を求めてください。会計にかかる時間は無視できます。

入力

$N\ L$
$x_1\ x_2\ \cdots \ x_N$
$y_1\ y_2\ \cdots \ y_N$

$1\le N \le 10^5$
$2N\lt L \le 10^9$
$0 \lt x_1 \lt x_2 \lt \cdots \lt x_N \lt L$
$0 \lt y_1 \lt y_2 \lt \cdots \lt y_N \lt L$
$x_i,y_j$はすべて異なる。
与えられる入力はすべて整数である。

出力

答えを表す数値を1行で出力してください。最後に改行してください。

サンプル

サンプル1
入力
3 7
1 2 4
3 5 6
出力
12

以下のようにすると最短の時間を達成できます。
・位置1にある寿司を食べる。
・位置3にあるお茶を飲む。
・位置4にある寿司を食べる。
・位置6にあるお茶を飲む。
・位置2にある寿司を食べる。
・位置5にあるお茶を飲み,退店する。

サンプル2
入力
2 5
1 3
2 4
出力
4

前から順に寿司とお茶を交互に消費することができます。

サンプル3
入力
10 827
47 129 132 290 308 309 540 544 656 818
119 241 332 340 376 498 575 632 699 737
出力
3640

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。