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 <cstdio>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <tuple>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using namespace std;
template <class T> inline void setmin(T & a, T const & b) { a = min(a, b); }
template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;

template <class T>
struct edge_t { int to; T cap, cost; int rev; };
template <class T>
void add_edge(vector<vector<edge_t<T> > > & graph, int from, int to, T cap, T cost) {
    graph[from].push_back((edge_t<T>) {   to, cap,  cost, int(graph[  to].size())     });
    graph[  to].push_back((edge_t<T>) { from,  0, - cost, int(graph[from].size()) - 1 });
}
/**
 * @brief minimum-cost flow with primal-dual method
 * @note mainly O(V^2UC) for U is the sum of capacities and C is the sum of costs. and additional O(VE) if negative edges exist
 */
template <class T>
T min_cost_flow_destructive(int src, int dst, T flow, vector<vector<edge_t<T> > > & graph) {
    T result = 0;
    vector<T> potential(graph.size());
    if (0 < flow) { // initialize potential when negative edges exist (slow). you can remove this if unnecessary
        whole(fill, potential, numeric_limits<T>::max());
        potential[src] = 0;
        while (true) { // Bellman-Ford algorithm
            bool updated = false;
            repeat (e_from, graph.size()) for (auto & e : graph[e_from]) if (e.cap) {
                if (potential[e_from] == numeric_limits<T>::max()) continue;
                if (potential[e.to] > potential[e_from] + e.cost) {
                    potential[e.to] = potential[e_from] + e.cost; // min
                    updated = true;
                }
            }
            if (not updated) break;
        }
    }
    while (0 < flow) {
        // update potential using dijkstra
        vector<T> distance(graph.size(), numeric_limits<T>::max()); // minimum distance
        vector<int> prev_v(graph.size()); // constitute a single-linked-list represents the flow-path
        vector<int> prev_e(graph.size());
        { // initialize distance and prev_{v,e}
            reversed_priority_queue<pair<T, int> > q; // distance * vertex
            distance[src] = 0;
            q.emplace(0, src);
            while (not q.empty()) { // Dijkstra's algorithm
                T d; int v; tie(d, v) = q.top(); q.pop();
                if (distance[v] < d) continue;
                // look round the vertex
                repeat (e_index, graph[v].size()) {
                    // consider updating
                    edge_t<T> e = graph[v][e_index];
                    int w = e.to;
                    T d1 = distance[v] + e.cost + potential[v] - potential[w]; // updated distance
                    if (0 < e.cap and d1 < distance[e.to]) {
                        distance[w] = d1;
                        prev_v[w] = v;
                        prev_e[w] = e_index;
                        q.emplace(d1, w);
                    }
                }
            }
        }
        if (distance[dst] == numeric_limits<T>::max()) return -1; // no such flow
        repeat (v, graph.size()) potential[v] += distance[v];
        // finish updating the potential
        // let flow on the src->dst minimum path
        T delta = flow; // capacity of the path
        for (int v = dst; v != src; v = prev_v[v]) {
            setmin(delta, graph[prev_v[v]][prev_e[v]].cap);
        }
        flow -= delta;
        result += delta * potential[dst];
        for (int v = dst; v != src; v = prev_v[v]) {
            edge_t<T> & e = graph[prev_v[v]][prev_e[v]]; // reference
            e.cap -= delta;
            graph[v][e.rev].cap += delta;
        }
    }
    return result;
}

int main() {
    int n; scanf("%d", &n);
    vector<int> a(n), b(n); repeat (i, n) scanf("%d%d", &a[i], &b[i]);
    map<int, int> compress;
    repeat (i, n) {
        compress.emplace(a[i], compress.size()); // nop if it already exists
        compress.emplace(b[i], compress.size());
    }
    auto edge = [&](int i) { return compress.size() + i; };
    const int src = compress.size() + n;
    const int dst = compress.size() + n + 1;
    vector<vector<edge_t<int> > > g(1 + compress.size() + n + 1);
    for (auto it : compress) {
        int compressed_a_i = it.second;
        add_edge(g, src, compressed_a_i, 1, 0);
    }
    repeat (i, n) {
        add_edge(g, compress[a[i]], edge(i), 1, - b[i]);
        add_edge(g, compress[b[i]], edge(i), 1, - a[i]);
        add_edge(g, edge(i), dst, 1, 0);
    }
    add_edge(g, src, dst, n, 0);
    int result = - min_cost_flow_destructive(src, dst, n, g);
    printf("%d\n", result);
    return 0;
}