#include <bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;
const int N = 1e5+4;
int a[N],b[N];
vector <int> v;
map <int,bool> m;
map <int,bool> m1;
int n;
signed main()
{
	ll s1 = 0,s2 = 0;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		scanf("%lld %lld",&a[i],&b[i]);
		s1 += a[i],
		s2 += b[i];

		v.push_back(a[i]);
		v.push_back(b[i]);
	}

	sort(v.begin(),v.end());
	ll S = 0,ans = min(s1,s2);
	// cout<<s1<<' '<<s2<<'\n';

	for(int i=0;i<n-2;i++)
	{
		// cout<<v[i]<<' ';
		S += v[i];
		m[v[i]] = true;
	}
	// cout<<S<<'\n';
	for(int i=1;i<=n;i++)
	{
		ll res = S + a[i] + b[i];
		m1[a[i]] = true;
		m1[b[i]] = true;
		int cnt = 0;
		if(m[a[i]] == true)
			res -= a[i],
			cnt++;

		if(m[b[i]] == true)
			res -= b[i],
			cnt++;


		if(cnt == 1)
		{
			if(m1[v[n-2]] == true)
				res += v[n-1];

			else
				res += v[n-2];
		}
		else if(cnt == 2)
			res += (v[n-2] + v[n-1]);

		ans = min(ans,res);
		m1[a[i]] = false;
		m1[b[i]] = false;

	}
	cout<<ans<<'\n';
}
### Prompt

Develop a solution in Cpp to the problem described below:

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 int long long
using namespace std;
const int N = 1e5+4;
int a[N],b[N];
vector <int> v;
map <int,bool> m;
map <int,bool> m1;
int n;
signed main()
{
	ll s1 = 0,s2 = 0;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		scanf("%lld %lld",&a[i],&b[i]);
		s1 += a[i],
		s2 += b[i];

		v.push_back(a[i]);
		v.push_back(b[i]);
	}

	sort(v.begin(),v.end());
	ll S = 0,ans = min(s1,s2);
	// cout<<s1<<' '<<s2<<'\n';

	for(int i=0;i<n-2;i++)
	{
		// cout<<v[i]<<' ';
		S += v[i];
		m[v[i]] = true;
	}
	// cout<<S<<'\n';
	for(int i=1;i<=n;i++)
	{
		ll res = S + a[i] + b[i];
		m1[a[i]] = true;
		m1[b[i]] = true;
		int cnt = 0;
		if(m[a[i]] == true)
			res -= a[i],
			cnt++;

		if(m[b[i]] == true)
			res -= b[i],
			cnt++;


		if(cnt == 1)
		{
			if(m1[v[n-2]] == true)
				res += v[n-1];

			else
				res += v[n-2];
		}
		else if(cnt == 2)
			res += (v[n-2] + v[n-1]);

		ans = min(ans,res);
		m1[a[i]] = false;
		m1[b[i]] = false;

	}
	cout<<ans<<'\n';
}
```