#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
 
const double EPS = 1e-10;
const ll INF = 100000000;
const ll MOD = 1000000007;

int n;
P x[200000];
P y[200000];
bool saw[200000];
ll ans;

int main() {
    cin >> n;
    rep(i,n) cin >> x[i].first >> x[i].second;
    rep(i,n) ans += x[i].first;
    ll tmp = 0;
    rep(i,n) tmp += x[i].second;
    ans = min(ans,tmp);
    rep(i,n) {
        y[i] = P(x[i].first,i);
        y[i+n] = P(x[i].second,i);
    }
    sort(y, y+2*n);
    tmp = 0;
    rep(i,n) {
        tmp += y[i].first;
        saw[y[i].second] = true;
    }
    rep(i,n) {
        if (!saw[i]) {
            cout << tmp << endl;
            return 0;
        }
    }
    for (int i = n; i < 2*n; i++) {
        if (y[i].second == y[n-1].second) {
            ans = min(ans, tmp-y[n-2].first+y[i].first);
        } else {
            ans = min(ans, tmp-y[n-1].first+y[i].first);
        }
    }
    cout << ans << endl;
}


### 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 rep(i,n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
 
const double EPS = 1e-10;
const ll INF = 100000000;
const ll MOD = 1000000007;

int n;
P x[200000];
P y[200000];
bool saw[200000];
ll ans;

int main() {
    cin >> n;
    rep(i,n) cin >> x[i].first >> x[i].second;
    rep(i,n) ans += x[i].first;
    ll tmp = 0;
    rep(i,n) tmp += x[i].second;
    ans = min(ans,tmp);
    rep(i,n) {
        y[i] = P(x[i].first,i);
        y[i+n] = P(x[i].second,i);
    }
    sort(y, y+2*n);
    tmp = 0;
    rep(i,n) {
        tmp += y[i].first;
        saw[y[i].second] = true;
    }
    rep(i,n) {
        if (!saw[i]) {
            cout << tmp << endl;
            return 0;
        }
    }
    for (int i = n; i < 2*n; i++) {
        if (y[i].second == y[n-1].second) {
            ans = min(ans, tmp-y[n-2].first+y[i].first);
        } else {
            ans = min(ans, tmp-y[n-1].first+y[i].first);
        }
    }
    cout << ans << endl;
}


```