Damaged Flowers

One day, a farmer left his ~N~ cows ~(2 \le N \le 100.000)~ to graze in the pasture, as usual. However, when he returned, he found them eating the flowers in his garden! Wanting to minimize the damage from now on, the farmer decided to immediately move each cow back to the barn.

Each cow ~i~ is at a position that is ~T_i~ minutes away ~(1 \le T_i \le 2.000.000)~ from the barn and destroys ~D_i\;(1 \le D_i \le 100)~ flowers per minute. No matter how hard he tries, the farmer can only move one cow at a time. Moving cow ~i~ requires a total of ~2~ ~\cdot~ ~T_i~ minutes (~T_i~ to take the cow to the barn and ~T_i~ to return).

The farmer starts from the garden, moves a cow to the barn, returns, and immediately moves the next cow.

Problem

Write a program that finds the order in which the farmer must move the cows so that the minimum possible number of flowers are destroyed.

Input

Line ~1~: contains the integer ~N~.

Lines ~2~ to ~N + 1~: each contains two integers separated by spaces, ~T_i~ and ~D_i~, describing the characteristics of cow ~i~.

Output

Line ~1~: contains a single number, the minimum number of damaged flowers.

Example of Input - Output Files:

STDIN (flowers.in)

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

STDOUT (flowers.out)

86

Constraints

• ~2 \le N \le 100.000~.
• ~1 \le T_i \le 2.000.000~.
• ~1 \le D_i \le 100~.