Description

Company L has $n$ factories distributed from high to low along a mountain; factory $1$ is at the summit, and factory $n$ is at the foot.

Because the mountain is in an inland plateau region (dry with little rain), Company L usually stacks products directly in the open air to save costs. One day, Mr. L, the president of Company L, received a call from the meteorological department and was informed that there would be a heavy rain in three days. Therefore, Mr. L decided to urgently build some warehouses at certain factories to prevent the products from getting wet.

Due to differences in terrain, the cost of building a warehouse may vary from one factory to another. Factory $i$ currently has $p_i$ finished items, and the cost of building a warehouse at factory $i$ is $c_i$.

For factories where no warehouse is built, their products should be transported to other warehouses for storage. Since Company L’s external sales outlet is located at factory $n$ at the foot of the mountain, products can only be transported downhill (that is, only to the warehouse of a factory with a larger index). Of course, transportation also costs money: transporting one item over one unit of distance costs $1$.

Assume that any warehouse built is large enough to hold all products. You will be given the following data:

• The distance from factory $i$ to factory $1$, $x_i$ (where $x_1 = 0$).
• The current number of finished items at factory $i$, $p_i$.
• The cost of building a warehouse at factory $i$, $c_i$.

Please help Company L find a warehouse construction plan that minimizes the total cost (construction cost + transportation cost).

Input Format

The first line contains an integer $n$, the number of factories.

Lines $2$ through $(n + 1)$ each contain three space-separated integers. On line $(i + 1)$, the integers are $x_i,~p_i,~c_i$ in order.

Output Format

Output a single line with one integer, the cost of the optimal plan.

3
0 5 10
5 3 100
9 6 10

32

Hint

Explanation for Sample Input/Output $1$

Build warehouses at factory $1$ and factory $3$. The construction cost is $10 + 10 = 20$, the transportation cost is $(9 - 5) \times 3 = 12$, and the total cost is $32$.

Constraints and Agreements

• For $20\%$ of the testdata, it is guaranteed that $n \leq 500$.
• For $40\%$ of the testdata, it is guaranteed that $n \leq 10^4$.
• For $100\%$ of the testdata, it is guaranteed that $1 \leq n \leq 10^6$, $0 \leq x_i,p_i,c_i < 2^{31}$.
• For any $1 \leq i < n$, it is guaranteed that $x_i < x_{i + 1}$.
• Let the answer be $ans$, and it is guaranteed that $ans + \sum\limits_{i = 1}^{n} p_ix_i < 2^{63}$.

Translated by ChatGPT 5