题目描述

维数轴上站着 $N$ 个人，编号$1 \sim N$

初始时，第$i$个人位于整数坐标位置 $P_i$，此人移动$1$单位距离所需的成本为 $W_i$，他能听到与他相距不超过 $D_i$,的所有位置发出的声音。

不同的人的位置可以重叠。

现在，我们需要选择一个整数坐标位置，并在此位置举办一场音乐会。

没有人想要错过这场音乐会，所以音乐会开始后，所有听不到音乐的人都会朝音乐会举办位置方向移动，直到移动至可以听到音乐的位置为止。

我们希望合理选择音乐会的举办位置，使得所有人的移动总成本尽可能小。

请你输出这个总成本的最小可能值。

输入

第一行包含一个整数 $N$。

接下来 $N$ 行，每行包含三个整数 $P_i,W_i,D_i$

输出

一个整数，表示最小总成本。

1
0 1000 0

0

样例解释

最佳方案是在位置 0举办音乐会，这样唯一的人无需任何移动即可听到音乐会。

2
10 4 3
20 4 2

20

样例解释

一种最佳方案是在位置 14 举办音乐会，这样的话，第一个人需要移动至位置 11，所需成本为(11-10)x4=4，第二个人需要移动至位置16，所需成本为(20-16)x4=16，总成本为4+16 =20。

3
6 8 3
1 4 1
14 5 2

43

提示

$1\leq N \leq 2 \times 10^5$

$0 \leq P_i \leq 10^9$

$1 \leq W_i \leq 1000$

$0 \leq D_i \leq 10^9$