While traveling on a critical mission, you’re tasked with reaching a window on the 126th floor of a towering building. To reach it, you have procured n rectangles to stack into a single tower.

Because earthquakes are common, the tower must obey these stability rules:

• Each rectangle must rest either on another rectangle or on the ground.
• Each rectangle may be placed either vertically or horizontally (rotation allowed).
• Only one rectangle may be placed directly on the ground.
• You may place rectangle B on top of rectangle A iff the side of B that touches A is strictly shorter than the supporting side of A.
• All rectangles must be used.

It is guaranteed there exists at least one way to stack all n rectangles while satisfying these rules. You want the tallest possible tower. Compute the maximum achievable height.

Input Format

• Line 1: integer n — the number of rectangles.
• Next n lines: two integers a and b — the length and width of the i-th rectangle.

Output Format

• Single line: a single integer — the maximum possible height of a valid tower.

Notes & Clarifications

• Rectangles can be rotated; choose the orientation that helps achieve maximum height.
• Only one rectangle may directly touch the ground.
• You must use all n rectangles. The input guarantees at least one valid stacking exists.
• Some rectangles may have identical dimensions.
• Constraints: 1 ≤ n ≤ 250,000, 1 ≤ a, b ≤ 10^9.

Example 1 Input

3
50000 160000
50000 100000
50000 100000

Example 1 Output

200000