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
Copy
3 4 1 5 10
1 2 3 4
1 2 5 7
1 2 6 8
2 3 9 10
Sample Output 1
Copy
94
Comments