#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mk make_pair
#define rint register int
using namespace std;
inline int read(){int w=1,s=0;char ch=getchar();while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}while(isdigit(ch)){s=s*10+ch-'0';ch=getchar();}return w*s;}
typedef pair<int,int> pa;
priority_queue<pa,vector<pa>,greater<pa> > q1;
priority_queue<pa> q2;
ll Sum=0,res=0;int n;int used[1000100];
int main()
{
	n=read();
	for(rint i=1;i<=n;++i)
	{
		int x=read(),y=read();
		q1.push(mk(x,i));q2.push(mk(y,i));
		Sum+=y,res+=x;
	}res=min(res,Sum);
	ll Sum1=0,Sum2=0,tot=0;
	for(rint i=1;i<n;++i)
	{
		pa tmp1=q1.top();q1.pop();
		if(!used[tmp1.second]) used[tmp1.second]=1,tot++;
		pa tmp2=q2.top();q2.pop();
		if(!used[tmp2.second]) used[tmp2.second]=1,tot++;
		Sum1+=tmp1.first;Sum2+=tmp2.first;
		if(tot>i)
		{
			res=min(Sum-Sum2+Sum1,res);
		}
		else 
		{
			if(!q1.empty()) res=min(res,Sum-Sum2+Sum1+q1.top().first-tmp1.first);
			if(!q2.empty()) res=min(res,Sum-Sum2+Sum1-q2.top().first+tmp2.first);
		}
	}cout<<res;
	return 0;
}



### Prompt

In CPP, your task is to solve 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<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mk make_pair
#define rint register int
using namespace std;
inline int read(){int w=1,s=0;char ch=getchar();while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}while(isdigit(ch)){s=s*10+ch-'0';ch=getchar();}return w*s;}
typedef pair<int,int> pa;
priority_queue<pa,vector<pa>,greater<pa> > q1;
priority_queue<pa> q2;
ll Sum=0,res=0;int n;int used[1000100];
int main()
{
	n=read();
	for(rint i=1;i<=n;++i)
	{
		int x=read(),y=read();
		q1.push(mk(x,i));q2.push(mk(y,i));
		Sum+=y,res+=x;
	}res=min(res,Sum);
	ll Sum1=0,Sum2=0,tot=0;
	for(rint i=1;i<n;++i)
	{
		pa tmp1=q1.top();q1.pop();
		if(!used[tmp1.second]) used[tmp1.second]=1,tot++;
		pa tmp2=q2.top();q2.pop();
		if(!used[tmp2.second]) used[tmp2.second]=1,tot++;
		Sum1+=tmp1.first;Sum2+=tmp2.first;
		if(tot>i)
		{
			res=min(Sum-Sum2+Sum1,res);
		}
		else 
		{
			if(!q1.empty()) res=min(res,Sum-Sum2+Sum1+q1.top().first-tmp1.first);
			if(!q2.empty()) res=min(res,Sum-Sum2+Sum1-q2.top().first+tmp2.first);
		}
	}cout<<res;
	return 0;
}



```