도장 모으기 Batch Compilation commands

IOI 철도 회사는 $N+2$개의 역으로 구성된 일직선 형태의 노선을 운영합니다. 이 노선의 역에는 한 쪽 끝 역에서부터 차례대로 $0$ 이상 $N+1$ 이하의 정수 번호가 붙어 있습니다.

이 노선에는 상행 열차와 하행 열차가 운행됩니다. 상행 열차를 타면 역 번호가 커지는 방향으로 이동할 수 있고, 하행 열차를 타면 역 번호가 작아지는 방향으로 이동할 수 있습니다. 열차를 타고 한 역에서 인접한 다른 역으로 이동하는 데 $T$초의 시간이 걸립니다. 즉 상행 열차를 타고 있는 동안에는 $i$번 역에서 $(i+1)$번 역까지 $T$초만에 이동할 수 있고, 하행 열차를 타고 있는 동안에는 $i$번 역에서 $(i-1)$번 역까지 $T$초만에 이동할 수 있습니다. 그러나 $N+1$번 역에서 상행 열차를 타거나 $0$번 역에서 하행 열차를 탈 수는 없습니다. 열차의 배차 간격은 매우 짧으므로 열차를 기다리는 시간은 무시해도 좋습니다.

각 역에는 상행 열차를 타는 플랫폼과 하행 열차를 타는 플랫폼이 있으며, 이 두 플랫폼을 연결하는 통로에 도장 찍는 곳이 있습니다.

현재 IOI 철도에서는 스탬프 랠리가 개최되고 있습니다. 이 스탬프 랠리는 $0$번 역의 플랫폼에서 출발하여 $1$번 $N$번 역까지 모든 도장을 다 찍은 후 $N+1$번 역의 플랫폼에 도착하면 완성됩니다.

각 역에서 도장을 찍기 위해 열차에서 내려 통로의 중간에 있는 도장 찍는 곳까지 걸어가야 합니다. $i$번 역에서 각 플랫폼과 도장 찍는 곳 사이를 이동하는 데 걸리는 시간은

• $i$번 역의 상행 열차 플랫폼에서 도장 찍는 곳까지 $U_{i}$초
• 도장 찍는 곳에서 $i$번 역의 상행 열차 플랫폼까지 $V_{i}$초
• $i$번 역의 하행 열차 플랫폼에서 도장 찍는 곳까지 $D_{i}$초
• 도장 찍는 곳에서 $i$번 역의 하행 열차 플랫폼까지 $E_{i}$초

입니다.

그러나 스탬프 랠리 참가자들은 $0$번 역과 $(N+1)$번 역에는 한 번만 방문할 수 있습니다. $1$번 역부터 $N$번 역까지는 몇 번이라도 방문할 수 있습니다.

$i$번 역의 구조

해야 할 일

도장 찍는 곳이 설치된 역의 개수, 기차로 한 역에서 인접한 다른 역으로 이동하는 데 걸리는 시간, 각 역의 상/하행 열차 플랫폼과 도장 찍는 곳 사이의 이동 시간이 주어집니다. 이 때 스탬프 랠리를 통과하는 데 걸리는 최소 시간을 구하는 프로그램을 작성하세요. 스탬프 랠리를 통과하는 데 걸리는 시간은 $0$번 역을 출발한 후 $N$개의 도장을 눌러 $(N+1)$번 역의 플랫폼에 도착하는 데 걸리는 시간입니다. 그러나 플랫폼에서 열차를 기다리는 시간이나 도장을 찍는 데 걸리는 시간은 무시해도 좋습니다.

입력 형식

표준 입력에서 아래 입력을 받으세요.

• 첫 번째 줄에 두 개의 정수 $N, T$가 공백을 사이로 두고 주어집니다. 이것은 역이 총 $(N+2)$개 있으며, 기차로 한 역에서 인접한 다른 역으로 이동하는 데 $T$초가 걸린다는 것입니다.
• 다음 $N$개 줄 중 $i$번째 줄 ($1 \le i \le N$)에는 네 개의 정수 $U_{i}, V_{i}, D_{i}, E_{i}$가 공백을 사이로 두고 주어집니다. 이 정수들은 아래와 같이 두 지점 사이를 이동하는 데 걸리는 시간을 나타냅니다.
  • $i$번 역의 상행 열차 플랫폼에서 도장 찍는 곳까지 $U_{i}$초
  • 도장 찍는 곳에서 $i$번 역의 상행 열차 플랫폼까지 $V_{i}$초
  • $i$번 역의 하행 열차 플랫폼에서 도장 찍는 곳까지 $D_{i}$초
  • 도장 찍는 곳에서 $i$번 역의 하행 열차 플랫폼까지 $E_{i}$초

출력 형식

표준 출력의 첫 번째 줄에 스탬프 랠리를 통과하는 데 걸리는 최소 시간을 초 단위로 나타낸 정수를 출력합니다.

제약 조건

모든 입력 데이터는 아래 조건을 만족합니다.

• $1 \le N \le 3,000$
• $1 \le T \le 100,000$
• $1 \le U_{i} \le 100,000$ ($1 \le i \le N$)
• $1 \le V_{i} \le 100,000$ ($1 \le i \le N$)
• $1 \le D_{i} \le 100,000$ ($1 \le i \le N$)
• $1 \le E_{i} \le 100,000$ ($1 \le i \le N$)

서브태스크

서브태스크 1 [10점]

• $N \le 16$

서브태스크 2 [75점]

• $N \le 100$

서브태스크 3 [15점]

추가 제약 조건이 없습니다.

예제

입력

4 1
1 1 1 1
1 9 9 1
9 9 1 1
1 9 9 1

출력

23

0번 역에서 출발하여 2번, 1번, 4번, 3번, 1번, 5번 역을 차례로 방문하면 최단 시간에 스탬프 랠리를 통과할 수 있습니다.

입력

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

출력

73