Lunch Concert

题目描述

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.

题意

有 $N$ 个人，第 $i$ 个人的速度为 $W_i$ 秒每米，听力为 $D_i$，即能听见距离他不超过 $D_i$ 米处的音乐，初始在 $P_i$ 位置。

你要在 $c$ 位置处开音乐会，这个 $c$ 由你决定且为整数。这 $N$ 个人都会靠近你直到能听到你。你要最小化每个人移动的时间之和。

输入格式

The first line of input contains $N$. The next $N$ lines contain three space-separated integers, $P_i, W_i$, and $D_i (1 ≤ i ≤ N)$. The following table shows how the available $15$ marks are distributed.

数据范围

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

输出格式

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.

样例 #1

样例输入 #1

1
0 1000 0

样例输出 #1

0

提示

样例解释1

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

样例解释2

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.