Problem Description

There are $N$ people, where the $i$-th person has a speed of $W_i$ seconds per meter, and a hearing range of $D_i$, meaning they can hear music from a distance of no more than $D_i$ meters away, initially located at position $P_i$.

You are to hold a concert at position $c$, which you can choose and must be an integer. All $N$ people will move closer to you until they can hear your music. You need to minimize the total time taken for everyone to move.

Input Format

The first line contains $N$.

The next $N$ lines each contain three integers: $P_i$, $W_i$, and $D_i$.

Output Format

Output a single integer, which is the minimum total time for everyone to move. (Note: The answer may exceed $2^{32}$.)

Sample Input and Output

Sample Input #1

1
0 1000 0

Sample Output #1

0

Sample Input #2

2
10 4 3
20 4 2

Sample Output #2

20

Sample Input #3

3
6 8 3
1 4 1
14 5 2

Sample Output #3

43

Notes

$$1 \leq N \leq 200000, 0 \leq P_i \leq 10^9, 1 \leq W_i \leq 1000, 0 \leq D_i \leq 10^9$$

Translated from CCC2021 S3.

Added a new hack data set on 2023.8.10.

见题面 Input 部分

见题面 Output 部分