Optimal Parking Strategy

There is a parking lot with ( n ) parking spaces arranged in a row with walls at both ends. There are also ( n ) cars that must park one by one in the lot. When the ( i)-th car parks, it chooses an empty parking space. Suppose that when parked, the number of consecutive empty parking spaces immediately to its left is ( l ) and to its right is ( r ) (stopping when a wall or an already parked car is encountered). The time needed for this car to park is [ T_i = W_i - L_i \cdot l - R_i \cdot r, ] where ( W_i, L_i, R_i ) are given for each car (and it is guaranteed that ( W_i \ge L_i\cdot n + R_i\cdot n ) so that ( T_i ) is nonnegative).

Your task is to decide, in order, the parking positions for the cars so that the total parking time is minimized.

Note that when a car parks, the consecutive empty spaces ( l ) (or ( r )) is defined in the following way: for a car parked in an empty segment, count the number of empty spaces immediately adjacent to it (to the left or right) until either a wall or another parked car is encountered.

One key observation is that there always exists an optimal strategy where the cars are inserted so that the occupied positions form a contiguous block. In such a strategy, after the first car chooses an arbitrary position ( p ) (and thus his gain is ( L_1\cdot (p-1)+R_1\cdot (n-p) )), subsequent cars extend the block either to the left or to the right. When extending, if the current parked block occupies positions ( [l,r] ) (with ( 1 \le l \le r \le n )), then:

• Parking on the left side (if ( l>1 )) puts the car at position ( l-1 ), and its left contiguous empty count is ( (l-1)-1 = l-2 ) (since the wall is at position 0 and position ( l ) is already occupied). The gain for that car is ( L_k \cdot (l-2) ), where ( k ) is the order of this car.

• Parking on the right side (if ( r<n )) puts the car at position ( r+1 ), and its right contiguous empty count is ( n - (r+1) = n - r - 1 ). The gain is ( R_k \cdot (n - r - 1) ).

If we denote the total parking time by ( \sum_{i=1}^n W_i ) minus the total gain (from having empty stretch available when parking), then minimizing the total parking time is equivalent to maximizing the total gain: [ \text{total_time} = \sum_{i=1}^{n} W_i - \text{total_gain}. ]

You are required to compute the minimal total time needed for parking all cars according to an optimal strategy.

inputFormat

The input begins with a single integer ( n ) (the number of parking spaces and cars). Then ( n ) lines follow. The ( i)-th of these lines contains three integers ( W_i ), ( L_i ), and ( R_i ), describing the parameters of the ( i)-th car. It is guaranteed that ( W_i \ge L_i \cdot n + R_i \cdot n ) for all ( i ).

outputFormat

Output a single integer — the minimal total time needed to park all ( n ) cars.

sample

1
10 1 1

10