스탬프 모으기

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$의 하행 승강장 사이를 이동하는 데 걸리는 시간은 다음과 같다.

• 역 $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 3000$.
• $1 \le T \le 100000$.
• $1 \le U_i \le 100000$ ($1 \le i \le N$).
• $1 \le V_i \le 100000$ ($1 \le i \le N$).
• $1 \le D_i \le 100000$ ($1 \le i \le N$).
• $1 \le E_i \le 100000$ ($1 \le i \le N$).