#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()

const int MN = 100010;

int N;
int A[MN], B[MN];
int cnt[MN];

int main() {
	cin >> N;
	vector<pii> vec;

	ll s1 = 0, s2 = 0;

	rep(i, N) {
		cin >> A[i] >> B[i];
		s1 += A[i];
		s2 += B[i];
		vec.eb(A[i], i);
		vec.eb(B[i], i);
	}

	ll ret = min(s1, s2);

	sort(ALL(vec));

	ll s = 0;
	ll d2 = 0;

	rep(i, N) {
		++cnt[vec[i].se];
		s += vec[i].fi;
		if (i < N-2) {
			d2 += vec[i].fi;
		}
	}

	rep(i, N) {
		ll t;
		if (cnt[i] == 2) {
			t = s;
		} else if (cnt[i] == 1) {
			t = s - min(A[i], B[i]);
			int p = N;
			while (true) {
				if (vec[p].se != i) {
					t += vec[p].fi;
					break;
				} else {
					p++;
				}
			}
		} else {
			t = d2 + A[i] + B[i];
		}
		ret = min(ret, t);
	}

	cout << ret << endl;

	return 0;
}
### Prompt

Construct a CPP code solution to the problem outlined:

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>
using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()

const int MN = 100010;

int N;
int A[MN], B[MN];
int cnt[MN];

int main() {
	cin >> N;
	vector<pii> vec;

	ll s1 = 0, s2 = 0;

	rep(i, N) {
		cin >> A[i] >> B[i];
		s1 += A[i];
		s2 += B[i];
		vec.eb(A[i], i);
		vec.eb(B[i], i);
	}

	ll ret = min(s1, s2);

	sort(ALL(vec));

	ll s = 0;
	ll d2 = 0;

	rep(i, N) {
		++cnt[vec[i].se];
		s += vec[i].fi;
		if (i < N-2) {
			d2 += vec[i].fi;
		}
	}

	rep(i, N) {
		ll t;
		if (cnt[i] == 2) {
			t = s;
		} else if (cnt[i] == 1) {
			t = s - min(A[i], B[i]);
			int p = N;
			while (true) {
				if (vec[p].se != i) {
					t += vec[p].fi;
					break;
				} else {
					p++;
				}
			}
		} else {
			t = d2 + A[i] + B[i];
		}
		ret = min(ret, t);
	}

	cout << ret << endl;

	return 0;
}
```