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
import bisect
import sys
input = sys.stdin.buffer.readline


n = int(input())
info = [list(map(int, input().split())) for i in range(n)]


sum_a = 0
sum_b = 0
for a, b in info:
    sum_a += a
    sum_b += b
ans = min(sum_a, sum_b)

res = []
for i in range(n):
    a, b = info[i]
    res.append(a)
    res.append(b)
res.sort()
min_half_sum = sum(res[0:n - 2])


for i in range(n):
    a, b = info[i]
    a, b = max(a, b), min(a, b)
    ind1 = bisect.bisect_right(res, a, lo=0, hi=2*n) - 1
    ind2 = bisect.bisect_right(res, b, lo=0, hi=ind1+1) - 1
    
    tmp_ans = min_half_sum
    cnt = 0
    if n - 2 <= ind1:
        tmp_ans += a
    else:
        cnt += 1
    if n - 2 <= ind2:
        tmp_ans += b
    else:
        cnt += 1

    for i in range(n - 2, 2 *n):
        if cnt == 0:
            break
        if i == ind1 or i == ind2:
            continue
        tmp_ans += res[i]
        cnt -= 1
    ans = min(tmp_ans, ans)

print(ans)