26455번 - Pizza delivery 다국어

문제

JAG Pizza is the famous pizza shop. Since the number of delivery orders has been increasing, it has been busier than before.

One day, several orders came to this shop at the same time! There were $N$ orders, and $N$ customers who placed the order. The $i$-th customer placed the $i$-th order.

Through past orders, this shop knows information for each customer. For the $i$-th customer, it takes $t_i$ hours for delivering the pizza from the shop, and also takes $t_i$ hours for going back to the shop. Moreover, his or her "irritability" is $a_i$. The bigger irritability a person has, the easier to be angry.

JAG Pizza has to deliver orders for customers, and keep their minds on less customer stress. To formulate the amount of stress which the $i$-th customer feels, let $h_i$ be the time from order to delivery, and let $p_i$ be the number of other customers whose delivery time is faster than that of $i$-th customer. The amount of stress for the $i$-th customer ($s_i$) is formulated as follows: $s_i = a_i \times (h_i + p_i)$.

For less customer stress, and gaining high satisfaction rates, a better delivery plan is necessary. When you think about it, you must take the following things into account:

• There is only one delivery person.
• A delivery person cannot deliver several orders in parallel. It means that he or she can deliver a single order at once, and when achieved, he or she gets back to the shop for delivering the next order.
• You can assume that it tooks no time for preparing an order, passing it from the shop to a delivery person, and passing it from a delivery person to a customer.

You are the delivery planner of JAG Pizza. Above these information and conditions, you have to minimize the total amount of stress for all customers.

입력

The input consists of a single test case of the following format.

$N$

$t_1$ $a_1$

$\vdots$

$t_N$ $a_N$

The first line is the number $N$ of customers (1ドル ≤ N ≤ 100,000円$).

The $i$-th of the following $N$ lines consists of two integers $t_i$ and $a_i,ドル which represent that it takes $t_i$ (1ドル ≤ t_i ≤ 1,000円$) hours for delivering the pizza from the shop to the $i$-th customer, and also takes $t_i$ hours for going back to the shop. Moreover, its irritability is $a_i$ (1ドル ≤ a_i ≤ 1,000円$).

출력

Print the minimum total amount of stress.

제한

힌트