On holiday in Australia, Nils finds himself without a means of transportation to get around the country! Luckily for him, there are cars which Nils is able to hire.
Australia is a weird place - the beaches are full of sunbathers at Christmas, people drive on the left side of the road, and there is only a single road which connects towns in a straight line from west to east.
The -th town from the west has a geographical position of
, representing the distance from the
-st town to the
-th town along the road in kilometres. This means the distance from the
-th town to the
-th town is
kilometres.
Furthermore, each of the towns contains exactly one car for hire. Nils can only change cars at these towns, and if he changes cars, he is unable to use the old car in the future. The -th town contains a car with enough fuel to travel
kilometres, and uses
dollars worth of fuel for each kilometre travelled. It also costs
extra dollars to hire the car. Once a car is hired, Nils cannot add any more fuel to the car.
Nils wants to get from the -st town to the
-th town as cheaply as possible. Initially, he does not have any car available. Can you help Nils determine the minimum total cost to reach the
-th town, only travelling by car?
Constraints
for
for
. This means that for that the
-th town is reachable from the
-th town using the
-th car, for
.
Subtask 1 [10%]
Subtask 2 [40%]
for
.
This means that every car can travel up to kilometres.
Subtask 3 [50%]
No additional constraints.
Note that all previous subtasks must be passed for this subtask to be evaluated.
Input Specification
The first line contains a single integer, representing the value of .
The -th of the following
lines contains four space-separated integers,
,
,
,
, representing the position, maximum distance, cost of fuel per kilometre and initial hiring cost of the
-th car.
Output Specification
On a single line, print the minimum possible total cost of reaching town , in dollars.
Sample Input
4
0 3 5 10
1 2 20 20
3 10 10 6
6 5 0 2
Sample Output
61
Explanation
Nils is forced to hire the car in the -st town, costing an initial hiring cost of
dollars.
Then, Nils should ride the car to the -rd town, travelling a distance of
kilometres. The cost of fuel for this leg of the journey is
dollars.
Nils should then hire the car in the -rd town, costing an initial hiring cost of
dollars.
Finally, Nils should ride this car to the -th town, travelling a distance of
kilometres. The cost of fuel for this leg of the journey is
dollars.
Overall, the total cost is dollars. It can be shown that this is the minimum possible total cost.
Comments