#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

The IOI railway is a straight line with **N** + 2 stations along the railway. Stations on the railway are numbered from 0 to **N** + 1 in one direction.

There are two types of trains running on the train routes: upward trains and downward trains. You can only take upward trains from one station to another station with a higher number, and similarly downward trains from one station to another station with a smaller number. It takes **T** seconds to move from one station to another station on both the upward and the downward trains. In other words, you can move from station **i** to station **i** + 1 in **T** seconds, and station **i** to station **i** - 1 in **T** seconds. However, you cannot take a downward train from station 0 or an upward train from station **N** + 1. The frequency of trains on the train routes is very high, so the time taken to wait for trains is negligible.

At each of the stations, there are two separate platforms, one for the upward trains and one for the downward trains. Between the two platforms, there is a stamp pad.

Currently, there is a stamp rally being held at the IOI railway. In this stamp rally, you must begin at station 0, collect stamps from all stations from stations 1 to **N**, and arrive at station **N** + 1.

In order to get the stamp at the station, it is necessary to leave the train and walk to the stamp pad in between the two platforms. The time taken to move to and from the two different types of trains and the stamp pad at each station differs:

- It takes
**U**seconds to move from the upward train platform at station_{i}**i**to the stamp pad. - It takes
**V**seconds to move from the stamp pad at station_{i}**i**to the upward train platform. - It takes
**D**seconds to move from the downward train platform at station_{i}**i**to the stamp pad. - It takes
**E**seconds to move from the stamp pad at station_{i}**i**to the down train platformward.

However, stamp rally participants are not able to visit station 0 and station **N** + 1 more than once, but are able to get on and off trains at stations 1 to **N** as many times as they wish.

Given the number of stations, the time it takes to move from one station to another, and the times it takes to travel to and from the upward and downward platforms to the stamp pad at each station, find the shortest time within which it is possible to complete the stamp rally.

The time it takes to clear the stamp rally is counted as the time it takes for you to begin at station 0, collect each of the stamps from stations 1 to **N**, and arrive at the upwards train platform of station **N** + 1. The time taken to wait for trains at platforms or to collect a stamp at the stamp pad is negligible.

### Input

Read from standard input.

- On the first line, there are two integers
**N**and**T**. This means there are**N**+ 2 stations and it takes**T**seconds to travel between stations on a train. - On the ith line of the next
**N**lines, there are four integers,**U**,_{i}**V**,_{i}**D**, and_{i}**E**. This means:_{i} - It takes
**U**seconds to move from the upward train platform at station_{i}**i**to the stamp pad. - It takes
**V**seconds to move from the stamp pad at station_{i}**i**to the upward train platform. - It takes
**D**seconds to move from the downward train platform at station_{i}**i**to the stamp pad. - It takes
**E**seconds to move from the stamp pad at station_{i}**i**to the down train platformward.

### Output

Print a single integer on a single line representing the shortest possible time required to complete the stamp rally in seconds.

### Constraints

All test cases satisfy the following constraints.

- 1 ≤
**N**≤ 3 000. - 1 ≤
**T**≤ 3 000. - 1 ≤
**U**≤ 100 000 (1 ≤_{i}**i**≤**N**). - 1 ≤
**V**≤ 100 000 (1 ≤_{i}**i**≤**N**). - 1 ≤
**D**≤ 100 000 (1 ≤_{i}**i**≤**N**). - 1 ≤
**E**≤ 100 000 (1 ≤_{i}**i**≤**N**).

### Subtasks

Subtask 1 (10 points):

**N**≤ 16 is satisfied.

Subtask 2 (75 points):

**N**≤ 100 is satisfied.

Subtask 3 (15 points):

No further constraints.

### Sample Input 1

```
4 1
1 1 1 1
1 9 9 1
9 9 1 1
1 9 9 1
```

### Sample Output 1

```
23
```

### Explanation

Setting out from station 0, visit stations 2, 1, 4, 3, 1, 5 in that order to complete the stamp rally in 23 seconds.

### Sample 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
```

### Sample Output 2

```
73
```

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 10 | 13 | 1s | 256MB | Minimum |

2 | 75 | 16 | 1s | 256MB | Minimum |

3 | 15 | 17 | 1s | 256MB | Minimum |

4 | 0 | 2 | 1s | 256MB | Minimum |

### Judge Compile Command

g++-8 ans.cpp -o stamps_joi -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512