Delivery Game


It's time to play. A group of students are about to play a game, this particular game consist of a group of students disposed on a line and a delivery point at the end of this line. The first student of the line has a package, so the goal of this game is simple: the package must be delivered to the delivery point(easy isn't it ?). The game start with the first student (the one with the package) running to the next student on the line; once he reach the next student, he can either keep going to the next student on the line or delivery the package to that student, and let him continues the way. This process repeats all along the way. Now the interesting part: every student have preparation time Pi (minutes required to take the package, put it in his knapsack, and get ready to leave) and a travel time Ti (minutes required to travel a single meter). The students wants to know the minimum time needed to delivery the package.


The datasets will consist of a number (1 ≤ N ≤ 1 000 000) the number of students in the line. Then follow N lines containing three integers Di, Pi and Ti, (1 ≤ Di, Pi, Ti ≤ 1 000 000) denoting the distance in meters to the delivery point, the preparation time in minutes and the travel time in minutes of the i-th student. Students are given in order (i.e. the first student in the dataset is the one with the package and the farther to the delivery point).


Print the minimum number of minutes needed to complete the delivery.

Example input:
5 3 2
4 3 1
1 2 1
Example output:
Time and memory limit:

  • 3s
  • 64MB

Problem source: Caribbean Online Judge