Migrated from Lutece 1045 Lovely princess

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

There are $n$ jobs you need to complete. However, complete the $i_{th}$ job you capability must be no less than $v_i$. If you have completed the $i_{th}$ job, your capability will increase $a_i$.

Then the question is coming, what is the minimum initial capability value if you are required to complete all of the $n$ jobs.

Note that there is no restriction on the order you complete them. That is to say, you can decide the order by your own.

Input

The first line contains a single integer $n$, which is the number of jobs you need to complete.

Then each of the following $n$ lines contains $2$ integers $v_i$ and $a_i$, which are described above.

$1 \leq n \leq 1000, 0 \leq v_i \leq 1000000, 0 \leq a_i \leq 1000$

Output

Print the answer in one line.

Samples

1
2 1

2

Resources

The 13th UESTC Programming Contest Preliminary