Minimizing Total Moving Time for a Concert

In this problem, there are (N) persons. The (i)-th person has a speed of (W_i) seconds per meter, a hearing distance of (D_i) meters (which means the person can hear music if they are within a distance of (D_i) from the source), and an initial position (P_i).

You are to decide an integer concert location (c) where the music will be played. All persons will move towards (c) until they are within their hearing distance (i.e. until (|P_i - c| \le D_i)). When a person is farther than (D_i) from (c), they must move a distance of (|P_i - c| - D_i). Thus, the time taken for the (i)-th person is (\max(0, |P_i - c| - D_i) \times W_i).

Your task is to choose (c) (an integer) to minimize the total moving time, i.e. the sum of the times taken by all persons.

inputFormat

The input begins with an integer (N) ((1 \le N \le 10^5)) indicating the number of persons. Each of the next (N) lines contains three integers (W_i), (D_i), and (P_i) representing, respectively, the speed (in seconds per meter), the hearing distance (in meters), and the initial position of the (i)-th person.

outputFormat

Output a single integer denoting the minimum total moving time.

sample

3
2 1 3
1 2 1
3 1 5

1