#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
struct pp
{
	ll x,y,id,idd;
}a[200005];
ll n,i,x,y,ans=0,ok=0,tot,t[2],bst1,bst2,buc[100005];
const ll inf=1e18;
bool cmp(pp a,pp b){return a.x<b.x;}
int main()
{
	scanf("%lld",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%lld%lld",&x,&y);
		a[i]=(pp){x,y,i,0};
		a[i+n]=(pp){y,x,i,1};
	}
	sort(a+1,a+2*n+1,cmp);
	for(i=1;i<=n;i++)
	{
		ans+=a[i].x;
		t[a[i].idd]++;
		buc[a[i].id]++;
		if(buc[a[i].id]==2)ok=1;
	}
	if(ok||t[0]*t[1]==0)printf("%lld\n",ans);
	else
	{
		bst1=-inf;tot=ans;
		bst2=ans=inf;
		for(i=1;i<=n;i++)
		{
			ans=min(ans,min(tot+a[i].y-bst1,tot-a[i].x+bst2));
			bst1=max(bst1,a[i].x);
			bst2=min(bst2,a[i].y);
		}
		printf("%lld\n",ans);
	}
	return 0;
}
### Prompt

Your challenge is to write 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>
using namespace std;
typedef long long ll;
struct pp
{
	ll x,y,id,idd;
}a[200005];
ll n,i,x,y,ans=0,ok=0,tot,t[2],bst1,bst2,buc[100005];
const ll inf=1e18;
bool cmp(pp a,pp b){return a.x<b.x;}
int main()
{
	scanf("%lld",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%lld%lld",&x,&y);
		a[i]=(pp){x,y,i,0};
		a[i+n]=(pp){y,x,i,1};
	}
	sort(a+1,a+2*n+1,cmp);
	for(i=1;i<=n;i++)
	{
		ans+=a[i].x;
		t[a[i].idd]++;
		buc[a[i].id]++;
		if(buc[a[i].id]==2)ok=1;
	}
	if(ok||t[0]*t[1]==0)printf("%lld\n",ans);
	else
	{
		bst1=-inf;tot=ans;
		bst2=ans=inf;
		for(i=1;i<=n;i++)
		{
			ans=min(ans,min(tot+a[i].y-bst1,tot-a[i].x+bst2));
			bst1=max(bst1,a[i].x);
			bst2=min(bst2,a[i].y);
		}
		printf("%lld\n",ans);
	}
	return 0;
}
```