We have a directed weighted graph with N vertices. Each vertex has two integers written on it, and the integers written on Vertex i are A_i and B_i.

In this graph, there is an edge from Vertex x to Vertex y for all pairs 1 \leq x,y \leq N, and its weight is {\rm min}(A_x,B_y).

We will consider a directed cycle in this graph that visits every vertex exactly once. Find the minimum total weight of the edges in such a cycle.

Constraints

* 2 \leq N \leq 10^5
* 1 \leq A_i \leq 10^9
* 1 \leq B_i \leq 10^9
* 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_N B_N


Output

Print the minimum total weight of the edges in such a cycle.

Examples

Input

3
1 5
4 2
6 3


Output

7


Input

4
1 5
2 6
3 7
4 8


Output

10


Input

6
19 92
64 64
78 48
57 33
73 6
95 73


Output

227
# -*- coding: utf-8 -*-
N = int(input())
pairs = []
for i in range(N):
    tmp = input()
    pairs.append([int(a) for a in tmp.split()])

pos_and_vals = []
for i, (from_, to_) in enumerate(pairs):
    pos_and_vals.append(((i, 0), from_))
    pos_and_vals.append(((i, 1), to_))

pos_and_vals_sorted = sorted(pos_and_vals, key=(lambda x: x[1]))
pos_and_vals_sorted_toN = pos_and_vals_sorted[:N]

directions = [[False, False] for _ in range(N)]
for (i, direction), val in pos_and_vals_sorted_toN:
    directions[i][direction] = True

smallest_sum = sum([val for (i, direction), val in pos_and_vals_sorted_toN])
first_direction = pos_and_vals_sorted[0][0][1]
if all([direction == first_direction for (i, direction), val in pos_and_vals_sorted_toN]):
    # if all to or all from
    # let it go
    answer = smallest_sum
elif any([(not direction[0]) and (not direction[1]) for direction in directions]):
    # if x exists and x is unused, then let it go
    answer = smallest_sum
else:
    highest_inner = pos_and_vals_sorted[N-1]
    lowest_outer = pos_and_vals_sorted[N]
    if highest_inner[0][0] != lowest_outer[0][0]:
        # replace and make it unused
        answer = smallest_sum - highest_inner[1] + lowest_outer[1]
    elif all([direction == lowest_outer[0][1]
              for (i, direction), val in pos_and_vals_sorted_toN[:N-1]]):
        # if all except target is all the same direction, then let it go
        answer = smallest_sum - highest_inner[1] + lowest_outer[1]
    else:
        assert N >= 2
        # candidates are only two
        second_highest_inner = pos_and_vals_sorted[N-2]
        second_lowest_outer = pos_and_vals_sorted[N + 1]
        candidate_one = smallest_sum - second_highest_inner[1] + lowest_outer[1]
        candidate_two = smallest_sum - highest_inner[1] + second_lowest_outer[1]
        answer = min(candidate_one, candidate_two)

print(answer)







