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
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskC solver = new TaskC();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskC {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int n = in.nextInt();
            long[] a = new long[2 * n];
            long[] sumHalf = new long[2];
            for (int i = 0; i < a.length; ++i) {
                int half = i % 2;
                int pos = i / 2;
                long cur = in.nextLong();
                a[i] = (cur * n + pos) * 2 + half;
                sumHalf[half] += cur;
            }
            long[] aOriginal = a.clone();
            Arrays.sort(a);
            int[] numHalf = new int[2];
            int[] numPos = new int[n];
            for (int i = 0; i < n; ++i) {
                int pos = (int) (a[i] / 2 % n);
                int half = (int) (a[i] % 2);
                ++numHalf[half];
                ++numPos[pos];
            }
            boolean ok = false;
            for (int i = 0; i < n; ++i) {
                if (numPos[i] == 0) {
                    ok = true;
                }
            }
            for (int i = 0; i < 2; ++i) {
                if (numHalf[i] == 0) {
                    ok = true;
                }
            }
            long s = 0;
            long max = 0;
            long max2 = 0;
            for (int i = 0; i < n; ++i) {
                long cur = a[i] / (2 * n);
                s += cur;
                if (cur > max) {
                    max2 = max;
                    max = cur;
                } else if (cur > max2) {
                    max2 = cur;
                }
            }
            if (!ok) {
                long best = Math.min(sumHalf[0], sumHalf[1]);
                for (int i = 0; i < n; ++i) {
                    long v1 = aOriginal[i * 2] / (2 * n);
                    long v2 = aOriginal[i * 2 + 1] / (2 * n);
                    long used = Math.min(v1, v2);
                    long got = s + Math.max(v1, v2);
                    if (used == max) got -= max2;
                    else got -= max;
                    best = Math.min(best, got);
                }
                s = best;
            }
            out.println(s);
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

    }
}

