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 .
The first line contains integers .
For the following lines, each line contains , indicating the information of train .
All of the test cases satisfy , , , , , , .
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