题目描述

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

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

输入格式

第一行：$N$。

接下来的 $N$ 行，每行依次包含 $P_i,W_i,D_i$。

输出格式

一个整数：每个人移动的时间之和的最小值。（答案保证不超过 $2^{32}$）

样例 #1

样例输入 #1

1
0 1000 0

样例输出 #1

0

样例 #2

样例输入 #2

2
10 4 3
20 4 2

样例输出 #2

20

样例 #3

样例输入 #3

3
6 8 3
1 4 1
14 5 2

样例输出 #3

43

提示

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