A single machine must run all n jobs, one after another with no gaps, in some order you choose. Job i needs t[i] units of processing time and carries a weight w[i]. If a job finishes at time C (the sum of processing times of all jobs up to and including it), it contributes w[i] * C to the cost.
Choose the order that minimizes the total cost, and output that minimum total cost.
Input format
Line 1: an integer n.
Next n lines: two integers t and w — the processing time and weight of one job.
Output format
A single integer: the minimum achievable value of the sum of w[i] * C[i] over all jobs.
Constraints
- 1 ≤ n ≤ 100000
- 1 ≤ t[i] ≤ 1000000
- 1 ≤ w[i] ≤ 1000000