The IOI Railway has a straight line of $N+2$ stations. The stations on this line are numbered from $0$ to $N+1$ in order from one end of the line.

There are two types of trains running on this line: northbound trains and southbound trains. A northbound train allows you to move in the direction of increasing station numbers, and a southbound train allows you to move in the direction of decreasing station numbers. It takes $T$ seconds to move between adjacent stations on these trains. That is, while on a northbound train, you can travel from station $i$ to station $i+1$ in $T$ seconds, and while on a southbound train, you can travel from station $i$ to station $i-1$ in $T$ seconds. However, you cannot board a northbound train at station $N+1$, nor can you board a southbound train at station $0$. The frequency of trains is very high, and the waiting time for a train can be ignored.

Each station has a platform for northbound trains and a platform for southbound trains. A stamp stand is located in the passage connecting these two platforms.

Currently, the IOI Railway is holding a stamp rally. In this stamp rally, you start at the northbound platform of station $0$, collect stamps from station $1$ to station $N$ one by one, and finish by arriving at the northbound platform of station $N+1$.

To collect a stamp at each station, you must get off the train and walk to the stamp stand located in the station's passage. The time required to move between the northbound platform, the stamp stand, and the southbound platform at station $i$ is as follows:

• From the northbound platform of station $i$ to the stamp stand: $U_i$ seconds
• From the stamp stand to the northbound platform of station $i$: $V_i$ seconds
• From the southbound platform of station $i$ to the stamp stand: $D_i$ seconds
• From the stamp stand to the southbound platform of station $i$: $E_i$ seconds

Participants in the stamp rally can visit station $0$ and station $N+1$ only once. Stations $1$ through $N$ can be visited any number of times.

Structure of station $i$

Task

Given the number of stations with stamps, the time taken to move between adjacent stations by train, and the time taken to move between the platforms and the stamp stand at each station, write a program to find the minimum time required to complete the stamp rally.

The time required to complete the stamp rally is the time from departing station $0$ until arriving at the northbound platform of station $N+1$ after collecting all $N$ stamps. Note that the time spent waiting for trains at platforms and the time spent stamping can be ignored.

Input

Read the following data from standard input:

• The first line contains two integers $N$ and $T$, separated by a space. This indicates that there are $N+2$ stations and it takes $T$ seconds to move between adjacent stations by train.
• The $i$-th line of the following $N$ lines ($1 \le i \le N$) contains four integers $U_i, V_i, D_i, E_i$, separated by spaces. This indicates:
  • $U_i$ seconds from the northbound platform of station $i$ to the stamp stand
  • $V_i$ seconds from the stamp stand to the northbound platform of station $i$
  • $D_i$ seconds from the southbound platform of station $i$ to the stamp stand
  • $E_i$ seconds from the stamp stand to the southbound platform of station $i$

Output

Output the minimum time required to complete the stamp rally in seconds as an integer on a single line.

Constraints

All input data satisfies the following conditions:

• $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$)

Subtasks

Subtask 1 [10 points]

• $N \le 16$

Subtask 2 [75 points]

• $N \le 100$

Subtask 3 [15 points]

• No additional constraints.

Examples

Input 1

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

Output 1

23

Note

The shortest time to complete the stamp rally is achieved by departing from station $0$ and visiting stations in the order: station $2$, station $1$, station $4$, station $3$, station $1$, station $5$.

Input 2

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

Output 2

73