Company L has $N$ factories distributed on a mountain from high to low. As shown in the figure, factory 1 is at the top of the mountain, and factory $N$ is at the foot of the mountain.

Since the mountain is located in an inland plateau region (dry and with little rain), Company L usually stores its products in the open air to save costs. Suddenly, one day, the president of Company L, Mr. L, receives a call from the meteorological department informing him that there will be a rainstorm in three days. Therefore, Mr. L decides to urgently build some warehouses at certain factories to prevent the products from being damaged by rain.

Due to the different terrain, the cost of building a warehouse at different factories may vary. The $i$-th factory currently has $P_i$ finished products, and the cost of building a warehouse at the location of the $i$-th factory is $C_i$. For factories where no warehouse is built, their products must be transported to other warehouses for storage. Since the sales department of Company L is located at factory $N$ at the foot of the mountain, products can only be transported downhill (i.e., they can only be transported to warehouses at factories with larger indices). Of course, transporting products also incurs costs. Assume that the cost of transporting one unit of product over one unit of distance is 1. Assume that the capacity of the built warehouses is large enough to hold all products.

You will be given the following data: The distance $X_i$ of factory $i$ from factory 1 (where $X_1=0$); The current quantity of finished products $P_i$ at factory $i$; * The cost $C_i$ of building a warehouse at factory $i$.

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

Input

The first line contains an integer $N$, representing the number of factories. The next $N$ lines each contain two integers $X_i, P_i, C_i$, with meanings as described in the problem.

Output

The output contains only one integer, which is the minimum cost for the optimal plan.

Examples

Input 1

3
0 5 10
5 3 100
9 6 10

Output 1

32

Note 1

If warehouses are built at factory 1 and factory 3, the construction cost is $10+10=20$, and the transportation cost is $(9-5) \times 3 = 12$, for a total cost of 32. If a warehouse is built only at factory 3, the construction cost is 10, and the transportation cost is $(9-0) \times 5 + (9-5) \times 3 = 57$, for a total cost of 67, which is not as good as the former.

Constraints

For 20% of the data, $N \le 500$; For 40% of the data, $N \le 10000$; For 100% of the data, $N \le 1000000$. All $X_i, P_i, C_i$ are within the range of 32-bit signed integers, and it is guaranteed that intermediate calculation results will not exceed 64-bit signed integers.