問題一覧 > 通常問題

No.808 Kaiten Sushi?

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 53
作問者 : sinsincoscossinsincoscos / テスター : noshi91noshi91
11 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

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。