小田赶牛

cow.in cow.out

题目描述

有 $n$ 头奶牛跑到了小田的花园里去爽吃花儿了，它们现在分别在距离牛圈 $T_{i}$（这里是指小田到那里需要 $T_{i}$ 分钟）处吃花，每分钟会吃掉 $D_{i}$ 朵花，小田现在要将它们弄回牛圈，但是他每次只能弄一头牛回去，来回用时总共为 $2 \times T_{i}$ 分钟，在这段时间内，其他的奶牛会继续吃小田的花，速度保持不变，当然正在被赶回牛圈的奶牛不能继续吃了。

作为一个喜欢花的人，小田自然想尽可能的让奶牛少吃花，所以现在小田想让你帮他设计一个赶牛的顺序，使得奶牛总共吃掉的花最少。

请输出奶牛最少会吃掉多少朵花。

输入描述

第一行输入一个整数 $n$，表示牛的数量。

接下来 $n$ 行，每行输入两个数字 $T_{i}$ 和 $D_{i}$，表示第 $i$ 头牛的距离和每分钟吃的花。

输出描述

输出包含一行一个整数，表示最终的答案。

输入输出样例

输入 #1

6
3 1
2 5
2 3
3 2
4 1
1 6

输出 #1

86

说明/提示

【样例 1 解释】

赶牛的顺序为 $6, 2, 3, 4, 1, 5$。

【数据范围】

对于 $10\%$ 的数据，有：所有牛的 $T_i \times D_i$ 相等。

对于另外 $10\%$ 的数据，有：所有牛的 $T_i$ 相等。

对于另外 $10\%$ 的数据，有：所有牛的 $D_i$ 相等。

对于所有测试数据，有：$1 \le n \le 10^{5}$，$1 \le T_{i} \le 2 \times 10^{6}$，$1 \le D_{i} \le 100$ 。