Yet Another Contest 2 P6 - Travel Budget

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 1.0s
Java 2.0s
Python 4.0s
Memory limit: 512M

Problem types

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?


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

0 3 5 10
1 2 20 20
3 10 10 6
6 5 0 2

Sample Output



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.


There are no comments at the moment.