Uolevi has n friends and each of them wants to order food from one of the restaurants in the city. None of Uolevi's friends owns any electronic device, so they all want to use Uolevi's cell phone. Given the amount of time the ith friend uses Uolevi's cell phone and the delivery time from the restaurant, compute the optimal order for Uolevi's friends to use his cell phone so that the time of last delivery is as early as possible. The delivery time for the order of the ith friend starts counting from the time the ith friend stops using the cell phone

Input

The first line of input contains integer n, the number of friends. Next n lines each contain two integers, a_i and b_i, the amount of time it takes for the ith friend to use Uolevi's phone and the delivery time for the order of the ith friend.

Output

Output one integer, the moment when the last delivery arrives if Uolevi's friends use optimal order.

Constraints

• 1 \le n \le 10^5
• 1 \le a_i \le 10^9
• 1 \le b_i \le 10^9

Example

Input:

3
3 2
4 8
1 2

Output:

12

In optimal strategy friend 2 orders first, then friend 3 and then friend 1. The arriving times are 12, 7 and 10.