17735번 - Collecting Stamps 서브태스크다국어

IOI 鉄道には N + 2 個の駅からなる一直線の路線がある．この路線の駅には，一方の端の駅から順に 0 か ら N + 1 までの番号がついている．

この路線には上り電車と下り電車の 2 種類の電車が走っている．上り電車に乗ると駅の番号が大きくな る方向に移動することができ，下り電車に乗ると駅の番号が小さくなる方向に移動することができる．こ れらの電車に乗って駅を 1 つ移動するためには T 秒の時間がかかる．すなわち，上り電車に乗っている間 は駅 i から駅 i + 1 まで T 秒で移動でき，下り電車に乗っている間は駅 i から駅 i − 1 まで T 秒で移動でき る．ただし，駅 N + 1 から上り電車に乗ることや，駅 0 から下り電車に乗ることはできない．電車の来る 頻度は非常に高く，電車を待つ時間は無視することができる．

それぞれの駅には，上り電車のホームと下り電車のホームがある．それらの 2 つのホームを結ぶ通路の 途中にスタンプ台が設置されている．

現在，IOI 鉄道ではスタンプラリーが開催されている．このスタンプラリーでは，駅 0 の上り電車のホー ムを出発して，駅 1 から駅 N のスタンプを 1 つずつ押し，駅 N + 1 の上り電車のホームに到着するとクリ アとなる．

各駅でスタンプを押すためには，電車から降りて駅の通路の途中にあるスタンプ台まで歩いていく必要 がある．駅 i の上り電車のホーム・スタンプ台・駅 i の下り電車のホームの間を移動するためにかかる時間 はそれぞれ，

• 駅 i の上り電車のホームからスタンプ台へは U_i 秒
• スタンプ台から駅 i の上り電車のホームへは V_i 秒
• 駅 i の下り電車のホームからスタンプ台へは D_i 秒
• スタンプ台から駅 i の下り電車のホームへは E_i 秒

である．

ただし，スタンプラリー参加者は，駅 0 と駅 N + 1 には 1 度しか訪れることができない．駅 1 から駅 N までの駅には何度でも降りることができる．

駅 i の構造

スタンプのある駅の個数，電車で駅を 1 つ移動するためにかかる時間，各駅の上り電車のホームとスタ ンプ台の間の移動にかかる時間，各駅の下り電車のホームとスタンプ台の間の移動にかかる時間が与えら れる．スタンプラリーをクリアするためにかかる時間の最小値を求めるプログラムを作成せよ．

スタンプラリーをクリアするためにかかる時間とは，駅 0 を出発してから，N 個のスタンプを押して， 駅 N + 1 の上り電車のホームに到着するまでにかかる時間のことである．ただし，ホームで電車を待つ時 間や，スタンプを押すのにかかる時間は無視してよい．

標準入力から以下のデータを読み込め．

• 1 行目には，整数 N, T が空白を区切りとして書かれている．これは，駅の数が N + 2 個あり，電車で 1 つ駅を移動するためにかかる時間が T 秒であることを表す．
• 続く N 行のうちの i 行目 (1 ≤ i ≤ N) には，整数 U_i, V_i, D_i, E_i が空白を区切りとして書かれている．こ れは，
  • 駅 i の上り電車のホームからスタンプ台へ U_i 秒
  • スタンプ台から駅 i の上り電車のホームへ V_i 秒
  • 駅 i の下り電車のホームからスタンプ台へ D_i 秒
  • スタンプ台から駅 i の下り電車のホームへ E_i 秒

で移動できることを表している．

標準出力に，スタンプラリーをクリアするためにかかる時間の最小値を秒単位で表す整数を 1 行で出力 せよ．

• 1 ≤ N ≤ 3 000．
• 1 ≤ T ≤ 100 000．
• 1 ≤ U_i ≤ 100 000 (1 ≤ i ≤ N)．
• 1 ≤ V_i ≤ 100 000 (1 ≤ i ≤ N)．
• 1 ≤ D_i ≤ 100 000 (1 ≤ i ≤ N)．
• 1 ≤ E_i ≤ 100 000 (1 ≤ i ≤ N)．