Problem Description

There are $N$ people. The $i$-th person has speed $W_i$ seconds per meter and hearing range $D_i$, meaning they can hear music within a distance of at most $D_i$ meters from them. They initially stand at position $P_i$.

You are going to hold a concert at position $c$, where $c$ is chosen by you and must be an integer. All $N$ people will move toward you until they can hear you. You want to minimize the sum of the time spent moving by everyone.

Input Format

The first line contains $N$.

The next $N$ lines each contain $P_i, W_i, D_i$ in order.

Output Format

Output one integer: the minimum possible sum of the time spent moving by everyone. (Note: the answer may exceed $2^{32}$.)

1
0 1000 0

0

2
10 4 3
20 4 2

20

3
6 8 3
1 4 1
14 5 2

43

Hint

$$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.

2023.8.10 Added a set of hack testdata.

Translated by ChatGPT 5