【问题描述】

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

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

我们认为，一旦$John$在牛栏处定位到要赶的某头牛后，首先会大喊一声，然后这头牛就失去了吃花的能力，乖乖的等待来将自己赶回牛栏。

【输入格式】

第一行一个数N。

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

【输出格式】

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

【样例输入】

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

【样例输出】

86

注释

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

FJ returns the cows in the following order: 6, 2, 3, 4, 1, 5. Whilehe 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. Forthe cows 3, 4, 1 he loses 16, 12, and 6 flowers respectively. Whenhe 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 <= N <= 100,000

1 <= T_i <= 2,000,000

1 <= D_i <= 100