408718: GYM103270 H Pet Pens (II)

George is building a massive pet store, so he can share his love of various animals with the rest of the world. However, he knows that certain pets are quite territorial and won't behave well if they don't have enough personal space.

Each pet will requires its own rectangular area of personal space. To deal with this, George has enlisted a contractor to build out a large $$$\textbf{square}$$$ pen that contains a subdivided rectangular pen for each pet. Each pet's subdivided pen must touch the southern border of the overall square pen, so that George has easy access to each pet. Each pet's rectangular enclosure can be rotated to fit within the square as long as one edge of the rectangle manages to touch the southern border.

Ideally, to cut down on costs, George wants to minimize the total side length of the entire square pen, but still build the square pen large enough that each pet has enough personal space disjoint from any other pet's personal space.

Given the $$$n$$$ pets at George's pet store and the rectangular areas that each pet requires, figure out the minimum total side length required to build out the total square pen for each pet.

The first line will consist of a single integer $$$n (1 \leq n \leq 10^5)$$$. The next $$$n$$$ lines will consist of two numbers $$$h_i$$$ and $$$w_i$$$ ($$$1 \leq h_i, w_i \leq 10^9$$$), which indicates that the $$$i$$$th pet requires a rectangular area of height $$$h_i$$$ and width $$$w_i$$$.

Output a single integer giving the minimal side length of the overall square pen that will fully contain each pet's required rectangular area.

1
1 1

1

3
2 4
4 3
3 1

6

In the first sample, the first pet only needs a single square of personal space, so a 1x1 square will suffice.

In the second sample, by placing the edge with length 2 of the first pet's space, the edge with length 3 of the second pet's space, and the edge of length 1 of the third pet's space along the southern border, we can fit all pets within a 6x6 square. No smaller square will fit these three pets.