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 <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>

using namespace std;
using ll = long long;
template <typename T>
constexpr T INF = numeric_limits<T>::max() / 10;

class CostFlow
{
public:
    using Cost = ll;
    using Ind = int;
    using Capacity = int;
    using T = ll;

    struct Edge {
        Edge(const Ind from_, const Ind to_, const Ind reverse_, const Capacity capacity_, const Cost cost_, bool is_reverse_ = false) : from{from_}, to{to_}, reverse{reverse_}, capacity{capacity_}, flow{0}, cost{cost_}, is_reverse{is_reverse_} {}
        Ind from;
        Ind to;
        Ind reverse;
        Capacity capacity;
        Capacity flow;
        Cost cost;
        bool is_reverse;
    };

    CostFlow(const Ind v) : V{v}
    {
        edge.resize(v);
        m_dist.resize(v);
        m_potential.resize(v);
        m_prev_v.resize(v);
        m_prev_e.resize(v);
    }

    void addEdge(const Ind from, const Ind to, const Capacity capacity, const Cost cost)
    {
        edge[from].push_back(Edge{from, to, (Ind)edge[to].size(), (Capacity)capacity, (Cost)cost, false});
        edge[to].push_back(Edge{to, from, (Ind)(edge[from].size() - 1), (Capacity)0, (Cost)(-cost), true});
    }

    T minCostFlow(const Ind s, const Ind t, T f)
    {
        using P = pair<Cost, Ind>;
        T res = 0;
        fill(m_potential.begin(), m_potential.end(), 0);

        // Bellman-Ford(Replace this when DAG)
        for (int i = 0; i < V; i++) {
            m_potential[i] = INF<T>;
        }
        m_potential[s] = 0;
        bool no_negative_loop = true;
        for (int i = 0; i < V; i++) {
            for (int v = 0; v < V; v++) {
                if (m_potential[v] != INF<T>) {
                    for (const auto& e : edge[v]) {
                        if (e.capacity <= 0) {
                            continue;
                        }
                        if (m_potential[e.to] > m_potential[v] + e.cost) {
                            m_potential[e.to] = m_potential[v] + e.cost;
                            if (i == V - 1) {
                                m_potential[e.to] = -INF<T>;  // Confirm " -INF < min(possible_cost) * V "
                                no_negative_loop = false;
                            }
                        }
                    }
                }
            }
        }
        if (not no_negative_loop) {
            // ????????¨?????????
        }

        while (f > 0) {
            // Dijkstra
            priority_queue<P, vector<P>, greater<P>> q;
            fill(m_dist.begin(), m_dist.end(), INF<T>);
            m_dist[s] = 0;
            q.push(make_pair(0, s));
            while (not q.empty()) {
                const P p = q.top();
                q.pop();
                const Ind v = p.second;
                if (m_dist[v] < p.first) {
                    continue;
                }
                for (Ind i = 0; i < edge[v].size(); i++) {
                    const auto& e = edge[v][i];
                    if (e.capacity > e.flow and m_dist[e.to] > m_dist[v] + e.cost + m_potential[v] - m_potential[e.to]) {
                        m_dist[e.to] = m_dist[v] + e.cost + m_potential[v] - m_potential[e.to];
                        m_prev_v[e.to] = v;
                        m_prev_e[e.to] = i;
                        q.push(make_pair(m_dist[e.to], e.to));
                    }
                }
            }
            if (m_dist[t] == INF<T>) {
                //                return -1;
                return res;
            }
            for (Ind v = 0; v < V; v++) {
                m_potential[v] += m_dist[v];
            }

            T d = f;
            for (Ind v = t; v != s; v = m_prev_v[v]) {
                const auto& e = edge[m_prev_v[v]][m_prev_e[v]];
                d = min(d, (T)(e.capacity - e.flow));
            }
            f -= d;
            res += d * m_potential[t];
            for (Ind v = t; v != s; v = m_prev_v[v]) {
                auto& e = edge[m_prev_v[v]][m_prev_e[v]];
                e.flow += d;
                edge[v][e.reverse].flow -= d;
            }
        }
        return res;
    }

    const Ind V;
    vector<vector<Edge>> edge;

private:
    vector<Cost> m_dist;
    vector<Cost> m_potential;
    vector<Ind> m_prev_v;
    vector<Ind> m_prev_e;
};

int main()
{
    int N;
    cin >> N;

    using P = pair<ll, ll>;
    vector<P> block(N);
    vector<ll> a;
    for (int i = 0; i < N; i++) {
        ll A, B;
        cin >> A >> B;
        block[i] = make_pair(A, B);
        a.push_back(A);
        a.push_back(B);
    }
    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());
    map<ll, int> b;
    for (int i = 0; i < a.size(); i++) {
        b[a[i]] = i + N + 1;
    }

    CostFlow flow(3 + N + a.size());
    const int s = 0;
    const int t = 1 + N + a.size();
    const int f = 2 + N + a.size();
    for (int i = 0; i < N; i++) {
        flow.addEdge(s, i + 1, 1, 0);
    }
    for (int i = 0; i < N; i++) {
        const auto& p = block[i];
        const int ind1 = b[p.first];
        const int ind2 = b[p.second];
        flow.addEdge(i + 1, ind1, 1, -p.second);
        flow.addEdge(i + 1, ind2, 1, -p.first);
        flow.addEdge(i + 1, f, 1, 0);
    }
    for (int i = 0; i < a.size(); i++) {
        flow.addEdge(N + 1 + i, t, 1, 0);
    }
    flow.addEdge(f, t, N, 0);
    cout << -flow.minCostFlow(s, t, 2 * N) << endl;


    return 0;
}