Problem Statement

Your company has $N$ employees, called Employee $1$ through $N$. You have received two work orders, called Work A and B, which must be completed. Employee $i$ can complete Work A in $A_i$ minutes and Work B in $B_i$ minutes.

You will assign each work to one employee. You can assign both works to the same employee, in which case the time it takes for him/her to complete them is the sum of the times it takes for him/her to do them individually. If you assign the works to different employees, the time it takes for them to complete them is the longer of the times it takes for them to do their respective works. Find the shortest possible time needed to complete the works.

Constraints

• $2 \le N \le 1000$
• $1 \le A_i \le 10^5$
• $1 \le B_i \le 10^5$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 B_1
A_2 B_2
A_3 B_3
\hspace{15pt} \vdots
A_N B_N

Output

Print the shortest possible time needed to complete the works, in minutes.