Minimizing Flower Damage

Farmer John has N cows in his garden that are eating his flowers. Each cow i is located T_i minutes away from its barn and destroys D_i flowers per minute while waiting. When FJ transports a cow, it takes exactly (2 \times T_i) minutes (T_i minutes to reach the barn and T_i minutes to return), during which the cow being transported stops eating flowers. However, the remaining cows continue to eat at their constant rate. The task is to determine the optimal order in which to transport the cows so as to minimize the total number of flowers destroyed.

To solve this problem, notice that if you transport a cow later, it will be subjected to the waiting time equal to the sum of the transportation times for the cows scheduled before it. Thus, if a cow has a high destruction rate (D_i), it is beneficial to transport it earlier. A swap analysis shows that for two cows i and j, it is optimal to have cow i before cow j if and only if (T_i \times D_j \le T_j \times D_i). This is equivalent to sorting the cows in increasing order of (\frac{T_i}{D_i}).

The output is the minimal total number of destroyed flowers given an optimal transportation order.

inputFormat

The first line contains a single integer N (2 ≤ N ≤ 100,000) representing the number of cows. Each of the next N lines contains two integers: T_i (1 ≤ T_i ≤ 2,000,000) and D_i (1 ≤ D_i ≤ 100), where T_i is the number of minutes to reach cow i’s barn and D_i is the number of flowers cow i destroys per minute.

outputFormat

Output a single integer: the minimum total number of flowers that will be destroyed if the cows are transported in an optimal order.

sample

3
1 3
2 2
3 1

10