Submit solution

Points: 7
Time limit: 1.0s
Memory limit: 64M

Author:
Problem types

It's time for Oliver to do his daily chores. There are N different types of chores. The i^\text{th} (1 \le i \le N) type takes Oliver a_i minutes to complete and there are b_i chores of that type. Oliver starts a stopwatch and gets right to work on the chores. Each time he completes a chore, he writes down the time in minutes on the stopwatch, and then immediately starts completing his next chore. Once he has completed all the chores, he calculates his efficiency score by adding up all the times he wrote down. Can you help Oliver minimize his efficiency score?

Input Specification

The first line will contain one integer N (1 \le N \le 10^5).

The next N lines will each contain two integers. The i^\text{th} (1 \le i \le N) line will contain a_i (1 \le a_i \le 10^9) and b_i (1 \le b_i \le 10^9).

Output Specification

Print one integer, the minimum efficiency score possible. Since this number may be very large, output it modulo 10^9 + 7.

Sample Input 1

3
2 1
4 3
1 2

Sample Output 1

43

Sample Input 2

1
100 1000000000

Sample Output 2

2100

Sample Input 3

5
6 3
2 4
1 1
10 12
3 4

Sample Output 3

1438

Comments

There are no comments at the moment.