In Byteland's train station, there are stations and trains in total. For each train, it will start from station at the moment and arrive at station at the moment . Note that we can only take the train at the moment as well as get off at the moment .

Starting from station , Kevin is going to station by train. To reach his destination, he can do multiple transfers. Specifically, we can transfer from train to train if and . In this case, Kevin will have to wait for moments and take train at the moment .

Let's evaluate Kevin's unhappiness as the value .

Each time when Kevin has to wait for moments in a transfer process, will be increased by ( are three given constraints). Specifically, we consider the process between the moment and the moment getting on the first train also as a transfer, which means the waiting time need to be taken into account.

Secondly, if Kevin reaches station at the moment of , will be increased by .

Please minimize Kevin's unhappiness value . We guarantee that there is at least one possible plan to arrive at station .

#### Input Specification

The first line contains integers .

For the following lines, each line contains , indicating the information of train .

#### Constraints

All of the test cases satisfy , , , , , , .

Test Case | Others | |||
---|---|---|---|---|

1~2 | None | |||

3~4 | ||||

5~8 | ||||

9 | ||||

10 | ||||

11~14 | None | None | ||

15 | ||||

16~17 | ||||

18~20 | None |

#### Output Specification

Please output an integer on one line, indication the minimum possible value of .

#### Sample Input 1

```
3 4 1 5 10
1 2 3 4
1 2 5 7
1 2 6 8
2 3 9 10
```

#### Sample Output 1

`94`

## Comments