## NOI '19 P1 - Route

View as PDF

Points: 25 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type

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 CaseOthers
1~2None
3~4
5~8
9
10
11~14NoneNone
15
16~17
18~20None

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