#include<cstdio>
#include<algorithm>
#include<set>
const int MaxN=100010;
int N;
struct item{int a,b;bool operator<(const item&it)const{return a<it.a;}}A[MaxN];
int main(){
	scanf("%d",&N);
	long long As=0,Bs=0,ans=0;
	for(int i=0;i<N;i++){
		scanf("%d%d",&A[i].a,&A[i].b);
		As+=A[i].a;
		Bs+=A[i].b;
		if(A[i].a>A[i].b){
			int t=A[i].a;
			A[i].a=A[i].b;
			A[i].b=t;
		}
	}
	ans=As<Bs?As:Bs;
	std::sort(A,A+N);
	As=Bs=0;
	for(int i=0;i<N;i++)As+=A[i].a;
	Bs=As+A[N-1].b-A[N-2].a;
	if(Bs<ans)ans=Bs;
	std::multiset<int>P,Q;
	for(int i=0;i<N;i++){
		P.insert(A[i].b);
	}
	Bs=0;
	for(int i=N;i--&&i>=N-i;){
		As-=A[i].a;
		if(Q.find(A[i].b)!=Q.end()){
			Q.erase(Q.find(A[i].b));
			Bs-=A[i].b;
		}
		else P.erase(P.find(A[i].b));
		while(Q.size()<N-i){
			int x=*P.begin();
			Q.insert(x);
			P.erase(P.find(x));
			Bs+=x;
		}
		if(As+Bs<ans)ans=As+Bs;
	}
	printf("%lld\n",ans);
}
### Prompt

Your task is to create a cpp solution to the following problem:

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

### Response

```cpp
#include<cstdio>
#include<algorithm>
#include<set>
const int MaxN=100010;
int N;
struct item{int a,b;bool operator<(const item&it)const{return a<it.a;}}A[MaxN];
int main(){
	scanf("%d",&N);
	long long As=0,Bs=0,ans=0;
	for(int i=0;i<N;i++){
		scanf("%d%d",&A[i].a,&A[i].b);
		As+=A[i].a;
		Bs+=A[i].b;
		if(A[i].a>A[i].b){
			int t=A[i].a;
			A[i].a=A[i].b;
			A[i].b=t;
		}
	}
	ans=As<Bs?As:Bs;
	std::sort(A,A+N);
	As=Bs=0;
	for(int i=0;i<N;i++)As+=A[i].a;
	Bs=As+A[N-1].b-A[N-2].a;
	if(Bs<ans)ans=Bs;
	std::multiset<int>P,Q;
	for(int i=0;i<N;i++){
		P.insert(A[i].b);
	}
	Bs=0;
	for(int i=N;i--&&i>=N-i;){
		As-=A[i].a;
		if(Q.find(A[i].b)!=Q.end()){
			Q.erase(Q.find(A[i].b));
			Bs-=A[i].b;
		}
		else P.erase(P.find(A[i].b));
		while(Q.size()<N-i){
			int x=*P.begin();
			Q.insert(x);
			P.erase(P.find(x));
			Bs+=x;
		}
		if(As+Bs<ans)ans=As+Bs;
	}
	printf("%lld\n",ans);
}
```