Lake Eleonora#10490
The renowned band "Lake Eleonora" is planning a concert along a coordinate line.
In the country where the concert will take place, there are residents. The -th resident lives at coordinate x_i, travels at a speed of one unit per w_i seconds, and can hear the concert if it is held within d_i units of their home.
The band needs to select an integer coordinate for the concert location. Residents who cannot hear the concert from their homes must travel to the concert site until they are within their hearing range (i.e., within d_i units).
Your task is to help the band determine a location that minimizes the total travel time for all residents to reach a point where they can hear the concert. However, you should output the minimum possible total travel time, not the location itself.
The first line contains a single integer (1 \leq n \leq 200\,000).
Each of the next lines contains three integers x_i, w_i, d_i (0 \leq x_i \leq 10^9, 1 \leq w_i \leq 1\,000, 0 \leq d_i \leq 10^9).
Output a single integer — the minimum possible total travel time.
Example 1
Example 2
Example 3
( points): n, x_i, d_i \leq 2\,000;
( points): x_i, d_i \leq 10^6;
( points): no additional constraints.