题目描述

农夫约翰去砍木头，像往常一样留下 $N$ 头牛吃草。当他回来时，惊恐地发现牛群正在他的花园里啃食美丽的花朵。为了尽量减少后续损失，约翰决定立即行动，把每头牛都运回各自的牛棚。

每头牛 $i$ 所在的位置距离自己的牛棚有 $T_i$ 分钟的路程。此外，在等待运输期间，它每分钟会破坏 $D_i$ 朵花。无论约翰怎么努力，他一次只能运送一头牛回牛棚。运送牛 $i$ 需要 $2 \times T_i$ 分钟 $T_i$ 分钟去牛棚， $T_i$ 分钟返回花园。约翰从花圃出发，运送完一头牛后会走回花圃，前往下一头需要运送的牛时不会额外花费时间。 请编写一个程序，确定约翰应该按什么顺序运送牛，以使被破坏的花朵总数最少。

输入格式

第一行，一个整数 $N\ (2 \leq N \leq 10^5)$ ，表示有多少头牛。

接下来的 $N$ 行，每行包含两个用空格分隔的整数 $T_i$ 和 $D_i\ (1 \leq T_i \leq 2\times 10^6,1 \leq D_i \leq 100)$，描述一头牛的属性

输出格式

一个整数，表示被破坏的花朵的最小总数

输入样例

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

输出样例

86