CF1151D Stas and the Queue at the Buffet

在 Kremland 王国科学中学的自助餐休息时间，形成了一条由 $n$ 名高中生组成的队列，编号从 $1$ 到 $n$。最初，每个学生 $i$ 站在第 $i$ 个位置。每个学生 $i$ 有两个特征值——$a_i$ 和 $b_i$。第 $i$ 个人的不满度等于 $a_i$ 乘以他左边的人数，加上 $b_i$ 乘以他右边的人数。形式化地说，若学生 $i$ 站在第 $j$ 个位置，则他的不满度为 $a_i \cdot (j-1) + b_i \cdot (n-j)$。 校长把一个任务交给了 Stas：重新排列队列中的人，使得总不满度最小。 虽然 Stas 能解决这样的问题，但这次他没有完成。他向你寻求帮助。

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$），表示队列中的人数。 接下来的 $n$ 行，每行包含两个整数 $a_i$ 和 $b_i$（$1 \leq a_i, b_i \leq 10^8$），分别表示第 $i$ 个学生的特征值。

输出一个整数，表示通过重新排列队列可以达到的最小总不满度。

在第一个样例中，最优的排列顺序为（$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$。 由 ChatGPT 4.1 翻译