It's lunchtime at your school! Your $N$ friends are all standing on a long field, as they usually do. The field can be represented as a number line, with the $i$-th friend initially at position $P_i$ metres along it. The $i$-th friend is able to walk in either direction along the field at a rate of one metre per $W_i$ seconds, and their hearing is good enough to be able to hear music up to and including $D_i$ metres away from their position. Multiple students may occupy the same positions on the field, both initially and after walking.

You're going to hold a little concert at some position $c$ metres along the field (where $c$ is any integer of your choice), and text all of your friends about it. Once you do, each of them will walk along the field for the minimum amount of time such that they end up being able to hear your concert (in other words, such that each friend $i$ ends up within $D_i$ units of $c$).

You'd like to choose $c$ such that you minimize the sum of all $N$ of your friends' walking times. What is this minimum sum (in seconds)? Please note that the result might not fit within a 32-bit integer.

The first line of input contains $N\ (1 \leq N \leq 200,000)$.
The next $N$ lines contain three space-separated integers, $P_i, W_i, D_i\ (0 \leq P_i \leq 1,000,000,000,\ 1 \leq W_i \leq 1,000,\ 0 \leq D_i \leq 1,000,000,000)$.

Output one integer which is the minimum possible sum of walking times (in seconds) for all $N$ of your friends to be able to hear your concert.

0

If you choose c=0, your single friend won't need to walk at all to hear it.

20

One possible optimal choice of c is 14, which would require your first friend to walk to position 11 (taking 4×1=4 seconds) and your second friend to walk to position 16 (taking 4×4=16 seconds), for a total of 20 seconds.