A desk must liquidate n positions. It can liquidate only one position at a time; liquidating position i occupies the desk for t_i minutes. Every position bleeds money while it is still on the book: position i costs c_i dollars per minute until the minute its liquidation is complete.

The desk starts at minute 0 and never idles. Choose the liquidation order that minimizes the total bleed, and output that minimum total cost.

Input

The first line contains the integer n. Each of the next n lines contains two integers t_i and c_i.

Output

One integer: the minimum total cost.

Constraints

1 <= n <= 10000

1 <= t_i, c_i <= 1000

Scoring

This is a standard problem: a submission scores full points if it produces the correct output for every test case, and zero otherwise.