Dereck is currently taking an online summer school course, but he has one big problem: he is an avid procrastinator who consistently submits all of his work exactly 0 seconds before it's due.

Being the good friend you are, can you help Dereck by telling him when he should be starting his work?

Given:

• ~N~ ~(1 \le N \le 400)~ assignments to do, due at the same time
• The number of hours, ~H~ ~(1 \le H \le 10~ ~000)~, it takes to complete each assignment
• And how many times, ~T~ ~(1 \le T \le 500)~, he has to do each assignment (He does assignments multiple times to procrastinate on doing other assignments)

How many hours before the due date should Dereck start his homework and assignments?

Input Specification

The first line will contain one integer, ~N~.

The following ~N~ lines will each contain two integers, ~H~ and ~T~.

Output Specification

Output the number of hours before the due date that Dereck should be starting his work.

Sample Input

5
1 2
3 1
4 4
3 1
5 3

Sample Output

39

Explanation

If Dereck starts 39 hours before the due date, he should finish exactly 0 seconds before it's due.