D. Jar Jar Thinks
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Jar Jar Binks wants to profit from his Jar Jar Drinks, so he opens a bar serving his galaxy-famous Jawa Juice. However, he isn't making much profit from selling drinks alone; so he had the great idea of adding food onto his menu. Jar Jar thinks, and he comes up with a great idea – pizza!

He gets his four-fingered hands on $$$n$$$ rectangular pizzas, where the $$$i$$$-th pizza is $$$w_i \times h_i$$$ inches. But Jar Jar Binks doesn't stop here. Jar Jar Binks loves four-sided regular polygons because four is the largest number he can count up to on his fingers. So the natural conclusion (for him) is to create the biggest square pizza possible!

Jar Jar Binks can do a few things to construct his big square pizza. Beforehand, he can rotate any of his $$$w_i \times h_i$$$ pizzas to become $$$h_i \times w_i$$$ pizzas. He can also cut off unnecessary pieces from any pizza to be reshaped to $$$w_i' \times h_i'$$$ where $$$0 \lt w_i' \le w_i$$$ and $$$0 \lt h_i' \le h_i$$$. Afterward, he can horizontally concatenate some or all of the pizzas to form the larger pizza. Note that any scraps cut off from a pizza are thrown away (into his belly) and the large concatenated pizza cannot be rotated.

But because Jar Jar stinks, he can't do the math to figure out how large he can make his square pizza! So he asks you this – What are the dimensions of the biggest $$$\textbf{square}$$$ pizza Jar Jar Binks can create?

Input

The first line contains one positive integer $$$n \: (1 \le n \le 10^5)$$$ – the number of pizzas Jar Jar Binks has.

Then $$$n$$$ lines follow. The $$$i$$$-th line contains 2 integers $$$a_i$$$, $$$b_i$$$ $$$(1 \le a_i, b_i \le 10^9)$$$, where $$$a_i$$$ denotes the width and $$$b_i$$$ denotes the length of the $$$i$$$-th pizza.

Output

Print one integer – the dimension of $$$1$$$ side of the biggest $$$\textbf{square}$$$ pizza.

Examples
Input
5
1 10
2 1
2 5
4 1
6 3
Output
5
Input
1
1000 1
Output
1
Note

In the first test case, notice that one way for Jar Jar Binks to create a $$$5 \times 5$$$ square pizza is to rotate the $$$6 \times 3$$$ pizza and concatenate it with the $$$2 \times 5$$$ pizza. Notice that Jar Jar Binks cannot create a larger square pizza as that would require vertical concatenation of pizzas, or is simply impossible.

Diagram of solution for test case 1.

In the second test case, notice that the largest square pizza Jar Jar Binks can create is a $$$1 \times 1$$$ square pizza.