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 needs 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, indicating 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