Protecting the Flowers

Farmer John went off to cut some wood and, as usual, left his N cows (2 ≤ N ≤ 100,000) grazing in the pasture. When he came back, he found to his horror that the herd had wandered into his garden and was eating his prized flowers. To limit the damage, John decided at once to carry the cows back to their barns one at a time.

Cow $i$ stands at a spot that is $T_i$ minutes (1 ≤ $T_i$ ≤ 2,000,000) from its barn. While it waits to be moved, cow $i$ tramples $D_i$ flowers (1 ≤ $D_i$ ≤ 100) per minute. John can carry only one cow at a time. Carrying cow $i$ to its barn takes $2 T_i$ minutes ($T_i$ to walk there and $T_i$ to walk back). John starts at the flower bed, carries a cow to its barn, and returns to the flower bed, spending no extra time before picking up the next cow.

While one cow is being carried to its barn, every cow that has not yet been moved keeps trampling flowers. Choose the order in which John carries the cows so that the total number of trampled flowers is as small as possible, and output that minimum total.

• Line 1: A single integer $N$.
• Lines 2..N+1: Each line contains two space-separated integers $T_i$ and $D_i$ describing one cow.

• Line 1: A single integer — the minimum possible number of trampled flowers.

In the example above, John moves the cows in the order 6, 2, 3, 4, 1, 5. While cow 6 is being carried, the remaining cows trample 24 flowers; while cow 2 is carried, 28 more; for cows 3, 4, and 1 the losses are 16, 12, and 6 flowers respectively. When cow 5 is carried, no other cow is left to trample flowers, so that step costs 0. The total is 24 + 28 + 16 + 12 + 6 = 86 flowers.