题目描述

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

他立即去把每头牛赶回它的牛栏。

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

数据范围
2 <= N <= 100,000
1 <= T_i <= 2,000,000
1 <= D_i <= 100

输入格式

第一行一个数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.