P2878 [USACO07JAN] Protecting the Flowers S

题目描述

有 $N$ 头奶牛跑到 FJ 的花园里去吃花儿了，它们分别在距离牛圈 $T_i$（这里指 FJ 到那里需要 $T_i$ 分钟) 处吃花，每分钟会吃掉 $D_i$ 朵花。

FJ 现在要将它们给弄回牛圈，但是他每次只能弄一头回去，来回用时总共为 $2 \times T_i$ 分钟，在这段时间内，其它的奶牛会继续吃 FJ 的花，速度保持不变，当然正在被赶回牛圈的奶牛不能继续吃了。

现在求在最好的方案下奶牛吃掉花的最少朵数。

输入格式

第一行一个整数 $N(1 \le N \le 10^5)$

下来 $N$ 行，每行两个整数 $Ti \ Di(2 \le T_i \le 2 \times 10^6,1 \le D_i \le 100)$ 。

输出格式

一行一个整数，即在最好的方案下奶牛吃掉花的最少朵数。

输入样例

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

输出样例

86

说明/提示

FJ returns the cows in the following order: 6, 2, 3, 4, 1, 5. While he is transporting cow 6 to the barn, the others destroy 24 flowers; next he will take cow 2, losing 28 more of his beautiful flora. For the cows 3, 4, 1 he loses 16, 12, and 6 flowers respectively. When he picks cow 5 there are no more cows damaging the flowers, so the loss for that cow is zero. The total flowers lost this way is 24 + 28 + 16 + 12 + 6 = 86.