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 sys
N=int(input())
A=0
B=0
table=[]
for i in range(N):
    a,b=map(int,input().split())
    table.append((a,i))
    table.append((b,i))
    A+=a
    B+=b
ans=min(A,B)
table.sort()
num=0
for i in range(N):
    num+=table[i][0]
L=[0]*N
#print(table)
for i in range(N):
    c,j=table[i]
    if L[j]!=0:
        ans=min(num,ans)
        print(ans)
        #print(L)
        sys.exit()
    L[j]+=1
c,n=table[N-1]
if n!=table[N][1]:
    num=num-table[N-1][0]+table[N][0]
    ans = min(num, ans)
    print(ans)
    sys.exit()
num1=num-table[N-1][0]+table[N+1][0]
num2=num-table[N-2][0]+table[N][0]
print(min(ans,num1,num2))


