← 返回题目列表

Codeforces · 1151/D

D. 员工和自助餐厅的队列

中文机器翻译题面 查看原题

在克里姆兰王国科学学院的自助餐休息期间,$$$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$$$。