在克里姆兰王国科学学院的自助餐休息期间,$$$n$$$高中生排起了长队,编号从$$$1$$$到$$$n$$$。最初,每个学生 $$$i$$$ 处于位置 $$$i$$$。每个学生 $$$i$$$ 都有两个数字 — $$$a_i$$$ 和 $$$b_i$$$。该人$$$i$$$的不满等于$$$a_i$$$乘以站在他位置左边的人数,加上$$$b_i$$$乘以站在他位置右边的人数。形式上,位于$$$j$$$位置的学生$$$i$$$的不满等于$$$a_i \cdot (j-1) + b_i \cdot (n-j)$$$。
导演委托斯塔斯的任务是:重新安排队列中的人,使总的不满情绪降到最低。
虽然斯塔斯能够解决这样的问题,但这并不是给他的。他向你求助。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — 队列中的人数。
以下 $$$n$$$ 行中的每一行都包含两个整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \leq a_i, b_i \leq 10^8$$$) - 学生 $$$i$$$ 的特征,最初位于 $$$i$$$ 位置。
输出
输出一个整数——通过重新排列队列中的人员可以实现的最小总不满度。
示例
输入 #1
3 4 2 2 3 6 1
输出 #1
12
输入 #2
4 2 4 3 3 7 1 2 3
输出 #2
25
输入 #3
10 5 10 12 4 31 45 20 55 30 17 29 30 41 32 7 1 5 5 3 15
输出 #3
1423
注意
在第一个示例中,最好按以下顺序排列人员:($$$3, 1, 2$$$)。第一个人处于$$$2$$$的位置,那么他的不满将等于$$$4 \cdot 1+2 \cdot 1=6$$$。第二个人处于$$$3$$$的位置,他的不满将等于$$$2 \cdot 2+3 \cdot 0=4$$$。第三个人处于$$$1$$$的位置,他的不满将等于$$$6 \cdot 0+1 \cdot 2=2$$$。总的不满将是$$$12$$$。
在第二个示例中,您需要按以下顺序放置人员:($$$3, 2, 4, 1$$$)。总的不满将是$$$25$$$。