题目描述

小珅同学最近迷上了各种闪闪发光的宝石，成为了一个新晋的宝石收藏家。小珅同学将所有的宝石都排成一列放在一个长长的回廊里，从编号 1 开始。

小珅同学每次去宝石市场都会买若干个相同的宝石，然后放到自己收藏的最末端。

现在有些朋友想来参观小珅同学的收藏，为了展现自己的富有，小珅同学想要对自己的宝石重新排列。

排序规则：

1. 不同种类的宝石平均单价越高越优先，相等时按照购买日期越小越优先；
2. 同种类且同价格的宝石购买日期越小越优先。

小珅同学想要求解出所有宝石编号变化的差值的绝对值之和，你能帮他计算吗？

注：宝石编号变化的差值绝对值。例如一个宝石在排序前编号 3，排完序之后编号 5，差值绝对值为 2。例如一个宝石在排序前编号 5，排完序之后编号 1，差值绝对值为 4。

输入格式

输入

第一行包含一个正整数 n（1≤n≤10⁵），代表小珅同学购买宝石的次数；

接下来 n 行每行包含三个整数 r、p、k，分别代表宝石的种类、购买的单价以及购买的数量（会出现种类相同但价格不同的宝石）。

1≤r,p≤10³，∑k≤10⁶，小珅同学买的所有宝石数量之和小于等于 10⁶。

输出格式

输出一个整数，宝石重新排列之后的差值绝对值之和。

输入样例 #1

3
8 1 3
4 10 2
10 1 2

输出样例 #1

12

输入样例 #2

5
1 7 2
8 16 2
1 34 1
8 16 2
8 6 1

输出样例 #2

4

输入样例 #3

5
2 4 2
8 19 2
2 31 1
5 10 2
8 3 1

输出样例 #3

18

提示

样例解释

样例给出三种不同的宝石的信息，对原先的宝石序列做好编号，表示为：1,2,3,4,5,6,7

先比较宝石的平均单价，已知计算公式为：平均单价 = 总价格 / 总数量

三种宝石的平均单价比较 3 / 3 = 2 / 2 < 20 / 2。

因为这三种宝石都没有同种类不同价格的情况，所以按照比较的结果优先将平均单价高的宝石放在序列前面，且同种宝石优先将购买日期近（编号更小）的放在前面，那么重新排列后的序列为：4,5,1,2,3,6,7

计算对应位置上编号的差值绝对值再求和：

abs(4−1)+abs(5−2)+abs(1−3)+abs(2−4)+abs(3−5)+abs(6−6)+abs(7−7)=3+3+2+2+2+0+0=12

数据范围

第一行包含一个正整数 n（1≤n≤10⁵），代表小珅同学购买宝石的次数；

1≤r,p≤10³，∑k≤10⁶，小珅同学买的所有宝石数量之和小于等于 10⁶。