题目描述

一天，黑猫老师给大橘同学布置了一道有趣的题目：“大橘同学，假设你有 $n$ 份文件需要按照特定顺序安装在磁带上，每份文件有它自己的大小 $a_i$，而且每份文件会被访问 $c_i$ 次。你能想办法安排文件的顺序，让总的访问时间最小吗？”

大橘同学听了之后，陷入了沉思。黑猫老师进一步解释道：“当要访问一份文件时，从磁带上最前面的文件开始，顺序找到你想要的文件，经过的所有文件的长度加起来，就是这次访问所消耗的时间。”

于是，大橘同学决定用自己的聪明才智解决这个问题。他发现，如果合理安排文件的顺序，可以让所有文件的累计访问时间最小。比如，假设磁带上的布局是将第 3 份文件放在前面，然后再放置第 1 和第 5 份文件，则：

• 单次访问第 3 份文件的时间为 $a_1 + a_5 + a_3$
• 累计访问第 3 份文件的时间为 $c_3 \cdot (a_1 + a_5 + a_3)$

黑猫老师对大橘同学说：“你需要安排磁带上文件的放置顺序，使得所有文件的累计访问时间最小。你能做得到吗？”

输入格式

• 第一行：单个整数表示 $n$
• 第二行到第 $n+1$ 行：每行两个整数 $a_i, c_i$

输出格式

• 单个整数：表示累计访问所有文件的最小总时间。

5
3 5
1 2
4 3
1 4
5 1

74

数据范围

• 30% 的数据，$1 \le n \le 10$
• 60% 的数据，$1 \le n \le 100$
• 100% 的数据，$1 \le n \le 10,\!000$
• $1 \le a_i \le 10,\!000$
• $1 \le c_i \le 10,\!000$