#include<cstdio>
#include<algorithm>
#include<set>
using namespace std;
#define int long long
const int N=200005;
struct D{int o,w,x;}d[N];
int n,va[2][N],b[2],a,r=1e18;bool v[2][N];
set<pair<int,int> >s;
bool cmp(D x,D y){return x.x<y.x;}
inline int mn(int x,int y){return x<y?x:y;}
signed main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;++i)
		scanf("%lld%lld",&d[i*2-1].x,&d[i*2].x),
		va[0][i]=d[i*2-1].x,va[1][i]=d[i*2].x,
		d[i*2-1].w=d[i*2].w=i,d[i*2-1].o=0,d[i*2].o=1;
	sort(d+1,d+n*2+1,cmp);
	for(int i=1;i<=n;++i)
		a+=d[i].x,++b[d[i].o],v[d[i].o][d[i].w]=1;
	if(b[0]==n||b[1]==n)return printf("%lld",a),0;
	for(int i=1;i<=n;++i)if(!v[0][i]&&!v[1][i])return printf("%lld",a),0;
	for(int i=n+1;i<=n*2;++i)s.insert(make_pair(d[i].x,d[i].w));
	for(int i=1;i<=n;++i)
		for(auto j=s.begin();j!=s.end();++j)
			if((*j).second!=i){r=mn(r,a+(*j).first-(v[0][i]?va[0][i]:va[1][i]));break;}
	return printf("%lld",r),0;
}
### Prompt

Please create a solution in Cpp 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>
using namespace std;
#define int long long
const int N=200005;
struct D{int o,w,x;}d[N];
int n,va[2][N],b[2],a,r=1e18;bool v[2][N];
set<pair<int,int> >s;
bool cmp(D x,D y){return x.x<y.x;}
inline int mn(int x,int y){return x<y?x:y;}
signed main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;++i)
		scanf("%lld%lld",&d[i*2-1].x,&d[i*2].x),
		va[0][i]=d[i*2-1].x,va[1][i]=d[i*2].x,
		d[i*2-1].w=d[i*2].w=i,d[i*2-1].o=0,d[i*2].o=1;
	sort(d+1,d+n*2+1,cmp);
	for(int i=1;i<=n;++i)
		a+=d[i].x,++b[d[i].o],v[d[i].o][d[i].w]=1;
	if(b[0]==n||b[1]==n)return printf("%lld",a),0;
	for(int i=1;i<=n;++i)if(!v[0][i]&&!v[1][i])return printf("%lld",a),0;
	for(int i=n+1;i<=n*2;++i)s.insert(make_pair(d[i].x,d[i].w));
	for(int i=1;i<=n;++i)
		for(auto j=s.begin();j!=s.end();++j)
			if((*j).second!=i){r=mn(r,a+(*j).first-(v[0][i]?va[0][i]:va[1][i]));break;}
	return printf("%lld",r),0;
}
```