An assembly line processes n items through two stages in series: every item is first machined at stage A, then at stage B. Both stages process items in the SAME chosen order (a permutation). Item i needs a[i] time at stage A and b[i] time at stage B. Stage A works on one item at a time; an item can begin stage B only after it has finished stage A and stage B is free. Stage A never idles between items it can start.
For a fixed order, the makespan is the time at which the last item finishes stage B. Choose the order that minimizes the makespan and output that minimum makespan.
Input format
Line 1: an integer n.
Next n lines: two integers a and b — the stage-A and stage-B times of one item.
Output format
A single integer: the minimum possible makespan.
Constraints
- 1 ≤ n ≤ 100000
- 1 ≤ a[i] ≤ 1000000
- 1 ≤ b[i] ≤ 1000000