题目描述

农夫$John$出去砍伐，让$N$头牛在草地上吃草。当他回来时吃惊的看到这些牛全部都跑到花园里在吃他的美丽花朵。他立即去把每头牛赶回它的牛栏。

$i$号牛每分钟要吃掉$D_i$朵花，距离自己的栏地要$T_i$分钟路程。不幸的是$John$每次只能赶一头牛回栏，再回到花园。请问这些牛最少要吃掉多少朵花？

输入格式

第一行一个数N。

下面$N$行，每行两个数$T_i$ $D_i$，表示第i头牛的数据。

输出格式

一个整数，最少吃掉的花朵数。

样例

input

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

output

86

注释

说明：最好方案赶回牛的次序为 6,2,3,4,1,5

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.

限制与提示

###数据范围

$2 \leq N \leq 100,000$

$1 \leq T_i \leq 2,000,000$

$1 \leq D_i \leq 100$