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 ~N~ towns in a straight line from west to east.

The ~i~-th town from the west has a geographical position of ~p_i~, representing the distance from the ~1~-st town to the ~i~-th town along the road in kilometres. This means the distance from the ~i~-th town to the ~j~-th town is ~|p_i-p_j|~ 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 ~i~-th town contains a car with enough fuel to travel ~s_i~ kilometres, and uses ~c_i~ dollars worth of fuel for each kilometre travelled. It also costs ~d_i~ 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 ~1~-st town to the ~N~-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 ~N~-th town, only travelling by car?

Constraints

~1 \le N \le 10^5~

~1 \le s_i, c_i, d_i \le 10^9~

~0 \le p_i \le 10^9~

~p_1 = 0~

~p_i < p_{i+1}~ for ~1 \le i < N~

~p_{i+1}-p_i \le s_i~ for ~1 \le i < N~. This means that for that the ~(i+1)~-th town is reachable from the ~i~-th town using the ~i~-th car, for ~1 \le i < N~.

Subtask 1 [10%]

~1 \le N \le 2000~

Subtask 2 [40%]

~s_i = 10^9~ for ~1 \le i \le N~.

This means that every car can travel up to ~10^9~ 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 ~N~.

The ~i~-th of the following ~N~ lines contains four space-separated integers, ~p_i~, ~s_i~, ~c_i~, ~d_i~, representing the position, maximum distance, cost of fuel per kilometre and initial hiring cost of the ~i~-th car.

Output Specification

On a single line, print the minimum possible total cost of reaching town ~N~, 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 ~1~-st town, costing an initial hiring cost of ~10~ dollars.

Then, Nils should ride the car to the ~3~-rd town, travelling a distance of ~|0-3| = 3~ kilometres. The cost of fuel for this leg of the journey is ~3 \times 5 = 15~ dollars.

Nils should then hire the car in the ~3~-rd town, costing an initial hiring cost of ~6~ dollars.

Finally, Nils should ride this car to the ~4~-th town, travelling a distance of ~|3-6| = 3~ kilometres. The cost of fuel for this leg of the journey is ~3 \times 10 = 30~ dollars.

Overall, the total cost is ~10+15+6+30 = 61~ dollars. It can be shown that this is the minimum possible total cost.