Problem : 366 - 2C. 集印問題

Problem Statistics

Solved Member: 1　　Submission: 2　　User Tried: 1

Statement:

某市的地下鐵恰好有 N+2 個站，這些站從一端到另外一端分別標號為 0,1,2,...,N,N+1。

地下鐵中有「正向電車」以及「反向電車」兩種電車，正向電車會從站 0 開始往 N+1 行駛，而反向則會由 N+1 往 0 行駛。這兩種電車在相鄰兩站中移動都需要花 T 的時間。由於電車來的頻率非常高，可以忽略等車所需要花費的時間。在每一個地下鐵站都有兩個月台分別可以搭稱正向和反向的電車，在連接這兩個月台的道路之間有一個集印台供旅客蓋章。

現在鐵道公司有了集印的活動，參加者必須以站 0 的正向電車月台為起點，收集完站 1 到站 N之間的所有印章，並抵達站 N+1 的正向月台就算完成活動。

為了能快速在每一站得到印章，你計算了第 i 站通道所需要花費的時間：
● 正向月台到集印台費時 Ui 秒
● 集印台到正向月台費時 Vi 秒
● 反向月台到集印台費時 Di 秒
● 集印台到反向月台費時 Ei 秒

(附圖：站 i 的構造)

集印過程中，你可以在抵達站 1 到 N 之間複數次，但是你只想經過站 0 和 N+1 一次就好。你想知道你需要花多少時間才能完成活動。

Input:Output:

第一行有兩個整數 N 和 T，代表有 N+2 站以及電車移動相鄰兩站所花的時間。
接下來 N 行中的第 i 行(1 ≤ i ≤ N) 每行有四個數字 Ui, Vi, Di, Ei。

限制：
1 ≤ N ≤ 3000
1 ≤ T, Ui, Vi, Di, Ei ≤ 100000

Subtask 1：(10分)
N ≤ 16

Subtask 2：(75分)
N ≤ 100

輸出一個整數，代表從活動開始完成活動最少需要花多久的時間。

Sample Input:Sample Output:

SAMPLE A:
4 1
1 1 1 1
1 9 9 1
9 9 1 1
1 9 9 1

SAMPLE B:
6 2
5 5 3 5
9 7 9 3
3 4 9 4
8 2 6 6
8 5 7 5
3 2 1 6

SAMPLE A:
23

SAMPLE B:
73

HINT:

SAMPLE 中，從站 0 出發，依序到達車站 2,1,4,3,1,5 可以在最短時間拿到所有印章。

Source:

2013/2014 JOI 合宿 2模（日本IOI國手考）

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0-1	1000ms	262144kb
0-2	1000ms	262144kb
1-1	1000ms	262144kb	10
1-2	1000ms	262144kb
1-3	1000ms	262144kb
1-4	1000ms	262144kb
1-5	1000ms	262144kb
1-6	1000ms	262144kb
1-7	1000ms	262144kb
1-8	1000ms	262144kb
1-9	1000ms	262144kb
1-10	1000ms	262144kb
1-11	1000ms	262144kb
1-12	1000ms	262144kb
1-13	1000ms	262144kb
2-1	1000ms	262144kb	75
2-2	1000ms	262144kb
2-3	1000ms	262144kb
2-4	1000ms	262144kb
2-5	1000ms	262144kb
2-6	1000ms	262144kb
2-7	1000ms	262144kb
2-8	1000ms	262144kb
2-9	1000ms	262144kb
2-10	1000ms	262144kb
2-11	1000ms	262144kb
2-12	1000ms	262144kb
2-13	1000ms	262144kb
2-14	1000ms	262144kb
2-15	1000ms	262144kb
2-16	1000ms	262144kb
3-1	1000ms	262144kb	15
3-2	1000ms	262144kb
3-3	1000ms	262144kb
3-4	1000ms	262144kb
3-5	1000ms	262144kb
3-6	1000ms	262144kb
3-7	1000ms	262144kb
3-8	1000ms	262144kb
3-9	1000ms	262144kb
3-10	1000ms	262144kb
3-11	1000ms	262144kb
3-12	1000ms	262144kb
3-13	1000ms	262144kb
3-14	1000ms	262144kb
3-15	1000ms	262144kb
3-16	1000ms	262144kb
3-17	1000ms	262144kb