题目描述

农夫$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

数据规模与约定

时间限制：$1 \text {s}$

空间限制：$256 \text {MB}$

注释

说明：最好方案赶回牛的次序为 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$