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=input()
pair=[]
sort=[]
for i in range(n):
	a, b=map(int, raw_input().split())
	pair.append([[a, 0], [b, 0]])
	sort.append((a, i, 0))
	sort.append((b, i, 1))
sum=0
sort.sort()
for i in range(n):
	assert pair[sort[i][1]][sort[i][2]][0]==sort[i][0]
	pair[sort[i][1]][sort[i][2]][1]=1
	sum+=sort[i][0]
cnt=[[0, 0], [0, 0]]
for i in range(n):
	cnt[pair[i][0][1]][pair[i][1][1]]+=1
assert cnt[0][0]==cnt[1][1]
if cnt[0][0]>0 or cnt[0][1]==n or cnt[1][0]==n:
	print sum
else:
	min_value=1000000000000000000
	max_value=-1
	for i in range(n):
		if pair[i][0][1]:
			assert pair[i][1][1]==0
			min_value=min(min_value, pair[i][1][0])
			max_value=max(max_value, pair[i][0][0])
		else:
			assert pair[i][1][1]==1
			min_value=min(min_value, pair[i][0][0])
			max_value=max(max_value, pair[i][1][0])
	min_id=-1
	max_id=-1
	for i in range(n):
		if pair[i][0][1]:
			assert pair[i][1][1]==0
			if min_value==pair[i][1][0]:
				min_id=i
			if max_value==pair[i][0][0]:
				max_id=i
		else:
			assert pair[i][1][1]==1
			if min_value==pair[i][0][0]:
				min_id=i
			if max_value==pair[i][1][0]:
				max_id=i
	assert min_value>=max_value
	if min_id!=max_id:
		print sum-max_value+min_value
	else:
		new_min_value=1000000000000000000
		new_max_value=-1
		for i in range(n):
			if i==min_id:
				continue
			if pair[i][0][1]:
				new_min_value=min(new_min_value, pair[i][1][0])
				new_max_value=max(new_max_value, pair[i][0][0])
			else:
				assert pair[i][1][1]==1
				new_min_value=min(new_min_value, pair[i][0][0])
				new_max_value=max(new_max_value, pair[i][1][0])
		print min(sum-max_value+new_min_value, sum-new_max_value+min_value)
		print>>sys.stderr, "\n\n\n"
