#include <bits/stdc++.h>

using namespace std;

const int N = 1e5+5;

#define x first
#define y second

int n;
pair< int, int > a[2*N];
pair< pair<int, int>, int > c[N];
long long l, r;

signed main() {
	l = r = 0;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d%d", &a[i*2].x, &a[i*2+1].x);
		c[i].x.x = a[i*2+1].x + a[i*2].x;
		c[i].x.y = min(a[i*2+1].x, a[i*2].x);
		a[i*2+1].y = a[i*2].y = c[i].y = i;
		l += a[i*2].x;
		r += a[i*2+1].x;
	}
	long long res = 0;
	sort(a, a+n+n);
	sort(c, c+n);
	set< int > lul;
	for (int i = 0; i < n; i++) {
		lul.insert(a[i].y);
		res += a[i].x;
	}
	if (lul.size() != n) {
		cout << min(res, min(r, l));
	}
	else {
		long long cur = res;
		if (a[n-1].y == c[0].y) {
			res = cur - a[n-2].x + c[0].x.x - a[n-1].x;
		}
		else {
			res = cur - a[n-1].x + c[0].x.x - c[0].x.y;
		}
		for (int i = 1; i < n; i++) {	
			if (a[n-1].y == c[i].y) {
				res = min(res, cur - a[n-2].x + c[i].x.x - a[n-1].x);
			}
			else {
				res = min(res, cur - a[n-1].x + c[i].x.x - c[i].x.y);
			}
		}
		cout << min(res, min(l, r));
	}
}
### 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>

using namespace std;

const int N = 1e5+5;

#define x first
#define y second

int n;
pair< int, int > a[2*N];
pair< pair<int, int>, int > c[N];
long long l, r;

signed main() {
	l = r = 0;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d%d", &a[i*2].x, &a[i*2+1].x);
		c[i].x.x = a[i*2+1].x + a[i*2].x;
		c[i].x.y = min(a[i*2+1].x, a[i*2].x);
		a[i*2+1].y = a[i*2].y = c[i].y = i;
		l += a[i*2].x;
		r += a[i*2+1].x;
	}
	long long res = 0;
	sort(a, a+n+n);
	sort(c, c+n);
	set< int > lul;
	for (int i = 0; i < n; i++) {
		lul.insert(a[i].y);
		res += a[i].x;
	}
	if (lul.size() != n) {
		cout << min(res, min(r, l));
	}
	else {
		long long cur = res;
		if (a[n-1].y == c[0].y) {
			res = cur - a[n-2].x + c[0].x.x - a[n-1].x;
		}
		else {
			res = cur - a[n-1].x + c[0].x.x - c[0].x.y;
		}
		for (int i = 1; i < n; i++) {	
			if (a[n-1].y == c[i].y) {
				res = min(res, cur - a[n-2].x + c[i].x.x - a[n-1].x);
			}
			else {
				res = min(res, cur - a[n-1].x + c[i].x.x - c[i].x.y);
			}
		}
		cout << min(res, min(l, r));
	}
}
```