## NOI '19 P1 - Route

View as PDF

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

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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