#include<bits/stdc++.h>
#define fo(i, x, y) for(int i = x, B = y; i <= B; i ++)
#define ff(i, x, y) for(int i = x, B = y; i <  B; i ++)
#define fd(i, x, y) for(int i = x, B = y; i >= B; i --)
#define ll long long
#define pp printf
#define hh pp("\n")
using namespace std;

const int N = 2e5 + 5;

int n, x, y, p[N], q[N], t[N][2];
struct P {
	int x, y, z;
	P(int _x = 0, int _y = 0, int _z = 0) {
		x = _x, y = _y, z = _z;
	}
} a[N]; int a0;

int cmpa(P a, P b) {
	return a.x < b.x;
}

ll s[N], ans;

int main() {
	scanf("%d", &n);
	ll sq = 0;
	fo(i, 1, n) {
		scanf("%d %d", &x, &y);
		ans += x; sq += y;
		if(x > y) swap(x, y);
		a[++ a0] = P(x, i, 0), a[++ a0] = P(y, i, 1);
		p[i] = x; q[i] = y;
	}
	if(sq < ans) ans = sq;
	sort(a + 1, a + a0 + 1, cmpa);
	fo(i, 1, a0) t[a[i].y][a[i].z] = i;
	fo(i, 1, a0) s[i] = s[i - 1] + a[i].x;
	fo(i, 1, n) {
		int x = t[i][0], y = t[i][1];
		if(x > n - 2) ans = min(ans, s[n - 2] + p[i] + q[i]); else
			if(x <= n - 2 && y > n - 1) ans = min(ans, s[n - 1] + q[i]); else
				ans = min(ans, s[n]);
	}
	pp("%lld\n", ans);
}
### 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>
#define fo(i, x, y) for(int i = x, B = y; i <= B; i ++)
#define ff(i, x, y) for(int i = x, B = y; i <  B; i ++)
#define fd(i, x, y) for(int i = x, B = y; i >= B; i --)
#define ll long long
#define pp printf
#define hh pp("\n")
using namespace std;

const int N = 2e5 + 5;

int n, x, y, p[N], q[N], t[N][2];
struct P {
	int x, y, z;
	P(int _x = 0, int _y = 0, int _z = 0) {
		x = _x, y = _y, z = _z;
	}
} a[N]; int a0;

int cmpa(P a, P b) {
	return a.x < b.x;
}

ll s[N], ans;

int main() {
	scanf("%d", &n);
	ll sq = 0;
	fo(i, 1, n) {
		scanf("%d %d", &x, &y);
		ans += x; sq += y;
		if(x > y) swap(x, y);
		a[++ a0] = P(x, i, 0), a[++ a0] = P(y, i, 1);
		p[i] = x; q[i] = y;
	}
	if(sq < ans) ans = sq;
	sort(a + 1, a + a0 + 1, cmpa);
	fo(i, 1, a0) t[a[i].y][a[i].z] = i;
	fo(i, 1, a0) s[i] = s[i - 1] + a[i].x;
	fo(i, 1, n) {
		int x = t[i][0], y = t[i][1];
		if(x > n - 2) ans = min(ans, s[n - 2] + p[i] + q[i]); else
			if(x <= n - 2 && y > n - 1) ans = min(ans, s[n - 1] + q[i]); else
				ans = min(ans, s[n]);
	}
	pp("%lld\n", ans);
}
```