Training is indispensable for achieving good results at ICPC. Rabbit wants to win at ICPC, so he decided to practice today as well.

Today's training is to gain dexterity that never mistypes by carefully stacking blocks. Since there are many building blocks, let's build a tall tower.

There are N blocks, and the i-th (1 ≤ i ≤ N) building blocks are in the shape of a rectangular parallelepiped of 1 x Ai x Bi. The side of length 1 is used in the depth direction, and the sides of lengths Ai and Bi are assigned one by one in the horizontal direction and one in the height direction. When building blocks, the upper building blocks must be exactly shorter in width than the lower building blocks. The blocks can be used in any order, and some blocks may not be used. Under these restrictions, I want to make the tallest tower that can be built.



Input


N
A1 B1
...
AN BN


Satisfy 1 ≤ N ≤ 1,000, 1 ≤ Ai, Bi ≤ 1,000,000. All input values ​​are integers.

Output

Output the maximum height of the tower on one line.

Examples

Input

3
10 40
10 40
20 30


Output

80


Input

4
1 2
2 3
3 4
4 1


Output

11
#include <bits/stdc++.h>

#define FOR(i,a,b) for(int i= (a); i<((int)b); ++i)
#define RFOR(i,a) for(int i=(a); i >= 0; --i)
#define FOE(i,a) for(auto i : a)
#define ALL(c) (c).begin(), (c).end()
#define RALL(c) (c).rbegin(), (c).rend()
#define DUMP(x)  cerr << #x << " = " << (x) << endl;
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v,x) (std::find(v.begin(), v.end(), x) != v.end())
#define BIT(n) (1LL<<(n))
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());

typedef long long LL;
template<typename T> using V = std::vector<T>;
template<typename T> using VV = std::vector<std::vector<T>>;
template<typename T> using VVV = std::vector<std::vector<std::vector<T>>>;
template<class T> inline T ceil(T a, T b) { return (a + b - 1) / b; }
template<class T> inline void print(T x) { std::cout << x << std::endl; }
template<class T> inline bool inside(T y, T x, T H, T W) {return 0 <= y and y < H and 0 <= x and x < W; }
inline double distance(double y1, double x1, double y2, double x2) { return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)); }

const int INF = 1L << 30;
const double EPS = 1e-9;
const std::string YES = "YES", Yes = "Yes", NO = "NO", No = "No";
const std::vector<int> dy = { 0, 1, 0, -1 }, dx = { 1, 0, -1, 0 };    // 4近傍（右, 下, 左, 上）

using namespace std;

// 最小費用流
class PrimalDual {
    struct Edge {
        const int to;         // 行き先のノードid
        int flow;             // 流量
        const int cap;        // 容量
        const int cost;       // コスト
        const int rev;        // 逆辺のノードid
        const bool is_rev;    // 逆辺かどうか
        Edge(int to, int flow, int cap, int cost, int rev, bool is_rev) : to(to), flow(flow), cost(cost), cap(cap), rev(rev), is_rev(is_rev) {
            assert(this->cap >= 0);
        }
    };

    // s-tまでの最短経路
    struct Route {
        vector<int> dist;     // 最短距離
        vector<int> prevv;    // 前の頂点
        vector<int> preve;    // 直前の辺
        vector<int> h;        // ポテンシャル
        Route(vector<int> &dist, vector<int> &prevv, vector<int> &preve, vector<int> &h) : dist(dist), prevv(prevv), preve(preve), h(h) {}
    };

    const unsigned long V;       // 頂点数
    vector<vector<Edge>> graph;  // グラフの隣接リスト表現
    vector<int> h;             // ポテンシャル
    vector<int> dist;          // 最短距離
    vector<int> prevv, preve;  // 直前の頂点と辺

public:
    PrimalDual(unsigned long num_of_node) : V(num_of_node) {
        graph.resize(V);
        h.resize(V, 0);
        dist.resize(V);
        prevv.resize(V);
        preve.resize(V);
    }

// sからtへの流量fの最小費用流を求める
    // 流せない場合は-1を返す
    int min_cost_flow2(int s, int t, int f) {
        int res = 0;

        while (f > 0) {

            // ダイクストラ法を用いてhを更新する
            priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> que;
            fill(dist.begin(), dist.end(), INT_MAX);
            dist[s] = 0;
            que.push(make_pair(0, s));
            while (not que.empty()) {
                pair<int, int> p = que.top();  // firstは最短距離, secondは頂点の番号
                que.pop();
                int v = p.second;
                if (dist[v] < p.first) {
                    continue;
                }
                for (int i = 0; i < graph[v].size(); ++i) {
                    Edge &e = graph[v][i];
                    if (e.cap - e.flow > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]) {
                        dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
                        prevv[e.to] = v;

                        preve[e.to] = i;
                        que.push(make_pair(dist[e.to], e.to));
                    }
                }
            }

            if (dist[t] == INT_MAX) {
                // これ以上流せない
                return res;
            }
            for (int v = 0; v < V; v++) {
                h[v] += dist[v];
            }
            // s-t間最短路に沿って目一杯流す
            int d = f;
            for (int v = t; v != s; v = prevv[v]) {
                d = min(d, graph[prevv[v]][preve[v]].cap - graph[prevv[v]][preve[v]].flow);
            }
            f -= d;
            res += d * h[t];
            for (int v = t; v != s; v = prevv[v]) {
                Edge &e = graph[prevv[v]][preve[v]];
                e.flow += d;
                graph[v][e.rev].flow -= d;
            }
        }
        return res;
    }

    // fromからtoへ向かう容量cap、コストcostの辺をグラフに追加する
    void add_edge(int from, int to, int cap, int cost) {
        graph[from].emplace_back(Edge(to, 0, cap, cost, graph[to].size(), false));
        graph[to].emplace_back(Edge(from, cap, cap, -cost, graph[from].size() - 1, true));
    }

    // sからtへの流量fの最小費用流を求める(流せない場合は-1)
    // O(F|E|log |V|)かO(F|V|^2)
    int min_cost_flow(int s, int t, int f) {
        int res = 0;

        while (f > 0) {
            Route route = dijkstra(s, t);
            vector<int> &dist = route.dist;
            vector<int> &prevv = route.prevv;
            vector<int> &preve = route.preve;
            vector<int> &h = route.h;

            // これ以上流せない
            if (dist[t] == INT_MAX) {
                return res;
                //return -1;
            }

            for (int v = 0; v < V; v++) {
                h[v] += dist[v];
            }

            // s-t間最短路に沿って目一杯流す
            int d = f;
            for (int v = t; v != s; v = prevv[v]) {
                int rest = graph[prevv[v]][preve[v]].cap - graph[prevv[v]][preve[v]].flow;
                d = min(d, rest);
            }
            f -= d;
            res += d * h[t];
            for (int v = t; v != s; v = prevv[v]) {
                Edge &e = graph[prevv[v]][preve[v]];
                e.flow += d;
                graph[v][e.rev].flow -= d;
            }
        }
        return res;
    }

    // sからtへの流量fの最小費用流(流せない場合は-1)
    // 負のコストがあってもいい
    // O(F|V||E|)
    int min_cost_flow_bellmanford(int s, int t, int f) {
        int res = 0;
        while (f > 0) {
            Route route = bellmanford(s, t);
            vector<int> &dist = route.dist;
            vector<int> &prevv = route.prevv;
            vector<int> &preve = route.preve;

            // これ以上流せない
            if (dist[t] == INT_MAX) {
                //return -1;
                return res; // 流せた分についての費用がほしいときはこっち
            }

            // s-t間最短路に沿って目一杯流す
            int d = f;
            for (int v = t; v != s; v = prevv[v]) {
                int rest = graph[prevv[v]][preve[v]].cap - graph[prevv[v]][preve[v]].flow;
                d = min(d, rest);
            }

            f -= d;
            res += d * dist[t];
            for (int v = t; v != s; v = prevv[v]) {
                Edge &e = graph[prevv[v]][preve[v]];
                e.flow += d;
                graph[v][e.rev].flow -= d;
            }
        }
        return res;
    }

    // 水の流れたエッジを取得する
    set<pair<int, int>> get_used_edges() {
        set<pair<int, int>> used_edges;
        for (int from = 0; from < this->graph.size(); ++from) {
            for (Edge edge : graph[from]) {
                int flow = edge.flow;
                bool is_rev = edge.is_rev;

                if (not is_rev and flow > 0) {
                    int to = edge.to;
                    used_edges.insert(make_pair(from , to));
                }
            }
        }
        return used_edges;
    }

private:
    // dijkstraでsからtへの最短ルートを求める
    Route dijkstra(int s, int t) {
        vector<int> dist(V, INT_MAX), prevv(V, 0), preve(V, 0), h(V, 0);

        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> que;
        dist[s] = 0;
        que.push(make_pair(0, s));
        while (not que.empty()) {
            pair<int, int> p = que.top();  // firstは最短距離, secondは頂点の番号
            que.pop();
            int v = p.second;
            if (dist[v] < p.first) {
                continue;
            }
            for (int i = 0; i < graph[v].size(); ++i) {
                Edge &e = graph[v][i];
                if (e.cap - e.flow > 0 and dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]) {
                    dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
                    prevv[e.to] = v;

                    preve[e.to] = i;
                    que.push(make_pair(dist[e.to], e.to));
                }
            }
        }

        return Route(dist, prevv, preve, h);
    }

    // bellmanfordでsからtへの最短ルートを求める
    Route bellmanford(int s, int t) {
        vector<int> dist(V, INT_MAX), prevv(V, 0), preve(V, 0), h(V, 0);

        // ベルマンフォード法により、s-t間最短路を求める
        dist[s] = 0;
        bool update = true;
        while (update) {
            update = false;
            for (int v = 0; v < V; v++) {
                if (dist[v] == INT_MAX) continue;
                for (int i = 0; i < graph[v].size(); i++) {
                    Edge &e = graph[v][i];
                    int rest = e.cap - e.flow;
                    int new_cost = dist[v] + e.cost;
                    if (rest > 0 and dist[e.to] > new_cost) {
                        dist[e.to] = new_cost;
                        prevv[e.to] = v;
                        preve[e.to] = i;
                        update = true;
                    }
                }
            }
        }

        return Route(dist, prevv, preve, h);
    }

};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N;
    cin >> N;
    V<int> A(N), B(N);
    set<int> value_set;
    FOR(i, 0, N) {
        cin >> A[i] >> B[i];
        value_set.insert(A[i]);
        value_set.insert(B[i]);
    }
    V<int> v(ALL(value_set));

    int s = v.size() + N;
    int t = s + 1;
    int dummy = t + 1;
    PrimalDual pd(v.size() + N + 3);

    FOR(i, 0, v.size()) {
        pd.add_edge(s, i, 1, 0);
        pd.add_edge(i, dummy, INF, 0);
    }

    FOR(i, 0, v.size()) {
        FOR(j, 0, N) {
            int a = A[j], b = B[j];
            if (v[i] == a) {
                pd.add_edge(i, v.size() + j, 1, -b);
            }
            if (v[i] == b) {
                pd.add_edge(i, v.size() + j, 1, -a);
            }
        }
    }

    FOR(j, 0, N) {
        pd.add_edge(v.size() + j, t, 1, 0);
    }
    pd.add_edge(dummy, t, INF, 0);


    cout << -1 * pd.min_cost_flow2(s, t, N * 2) << endl;
    return 0;
}
