【题目描述】

小灰灰正在组织同学们排队完成任务。共有 $n$ 个同学，第 $i$ 个同学完成任务需要 $t_i$ 单位时间。

如果一个同学在开始完成任务之前等待了 $x$ 单位时间，那么他会产生 $w_i \times x$ 的不满意度，其中 $w_i$ 表示第 $i$ 个同学每等待 $1$ 单位时间产生的不满意度。

你可以任意安排这 $n$ 个同学完成任务的顺序。请你求出所有同学不满意度之和的最小值。

---

【输入描述】

第一行输入一个整数 $n$。

接下来 $n$ 行，每行输入两个整数 $t_i,w_i$，表示第 $i$ 个同学完成任务需要的时间，以及每等待 $1$ 单位时间产生的不满意度。

保证：

• $1\le n\le 2\times 10^5$；
• $1\le t_i,w_i\le 10^9$；
• 对于所有正式测试数据，最小总不满意度不超过 $9\times 10^{18}$。

---

【输出描述】

输出一行一个整数，表示最小的总不满意度。

---

【样例 1】

【样例 1 输入】

3
3 1
1 3
2 2

【样例 1 输出】

5

【样例 1 解释】

一种最优顺序是让第 $2$ 个同学、第 $3$ 个同学、第 $1$ 个同学依次完成任务。

此时三位同学的等待时间分别为 $0,1,3$，总不满意度为：

$$3\times 0+2\times 1+1\times 3=5。$$

---

【样例 2】

【样例 2 输入】

5
10 3
2 8
6 4
3 9
7 2

【样例 2 输出】

113

【样例 2 解释】

一种最优顺序是第 $2,4,3,1,5$ 个同学。

---

【样例 3】

见选手目录下的 Data/sample3.in 和 Data/sample3.ans。

该样例满足 $n\le 8$。

---

【样例 4】

见选手目录下的 Data/sample4.in 和 Data/sample4.ans。

该样例满足所有 $w_i=1$。

---

【样例 5】

见选手目录下的 Data/sample5.in 和 Data/sample5.ans。

该样例仅满足完整数据范围，无额外限制。

---

【数据规模与约定】

测试点编号	分数	特殊性质
1 ~ 3	15	$n\le 8$
4 ~ 5		所有 $w_i=1$
6 ~ 7		所有 $t_i=1$
8 ~ 10	20	$n\le 5000$ 且 $t_i,w_i\le 1000$
11 ~ 12	15	$t_i,w_i\le 4\times 10^4$
13 ~ 15	20	无额外限制

对于 $100\%$ 的数据，满足 $1\le n\le 2\times 10^5$，$1\le t_i,w_i\le 10^9$，且最小总不满意度不超过 $9\times 10^{18}$。

点击下载本题选手目录