题目描述

有 $n$ 份文件需要安置在磁带上，第 $i$ 份文件的长度为 $a_i$，它会被访问 $c_i$ 次。

当要访问一份文件时，要从磁带上最靠前的文件开始，顺序找到这份文件为止，单次访问的时间就是经过的文件的总长度之和。

你需要在磁带上安排文件的放置顺序，使得所有文件累计访问时间的总和最小。

例如假设磁盘的布局是在第 $3$ 份文件之前还放置了第 $1$ 与第 $5$ 份文件，则

• 单次访问第 $3$ 份文件的时间为 $(a_1+a_5+a_3)$，
• 累计访问第 $3$ 份文件的时间为 $c_3(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

样例解释 1

文件4 → 文件2 → 文件1 → 文件3 → 文件5 总时间：4 + 4 + 25 + 27 + 14 = 74

数据范围

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