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 <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef pair<int,int> pint;

#define DE 1
#define FI first
#define SE second
#define PB push_back
#define MP make_pair
#define ALL(s) (s).begin(),(s).end()
#define REP(i,n) for (int i = 0; i < (int)(n); ++i)
#define EACH(i,s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define COUT(x) cout<<#x<<" = "<<(x)<<" (L"<<__LINE__<<")"<<endl

template<class T1, class T2> ostream& operator<<(ostream &s, pair<T1,T2> P){return s<<'<'<<P.first<<", "<<P.second<<'>';}
template<class T> ostream& operator<<(ostream &s, vector<T> P) {s<<"{ ";for(int i=0;i<P.size();++i){if(i>0)s<<", ";s<<P[i];}return s<<" }"<<endl;}
template<class T1, class T2> ostream& operator<<(ostream &s, map<T1,T2> P) {s<<"{ ";for(__typeof__(P.begin()) it=P.begin();it!=P.end();++it){if(it!=P.begin())s<<", ";s<<'<'<<it->first<<"->"<<it->second<<'>';}return s<<" }"<<endl;}



struct Edge {
    int rev, from, to, cap, icap, flow, cost;
    Edge() {}
    Edge(int r, int f, int t, int ca, int co) : rev(r), from(f), to(t), cap(ca), icap(ca), flow(0), cost(co) {}
    friend bool operator < (const Edge &e1, const Edge &e2) {return e1.cost < e2.cost;}
    friend ostream& operator << (ostream& s, const Edge& E) {s << E.from << "->" << E.to << '(' << E.cap << ',' << E.cost << ')';return s;}
};

const int MAX_V = 5000;
struct Graph {
    int V,E;
    vector<Edge> list[MAX_V];
    
    Graph(int n = 0) : V(n), E(0) {}
    void init(int n = 0) {V = n; E = 0; for (int i = 0; i < MAX_V; ++i) list[i].clear();}
	void resize(int n = 0) {V = n;}
    void reset() {for (int i = 0; i < V; ++i) for (int j = 0; j < list[i].size(); ++j) list[i][j].cap = list[i][j].icap;}
    inline vector<Edge>& operator [] (int i) {return list[i];}
    friend ostream& operator << (ostream& s, const Graph& G) {for (int i = 0; i < G.V; ++i) {s << i << " : " << G.list[i];}return s;}
    
    void addedge(int from, int to, int cap, int cost) {
        if (cap > 0) {
            ++E;
            list[from].push_back(Edge(list[to].size(), from, to, cap, cost));
            list[to].push_back(Edge(list[from].size()-1, to, from, 0, -cost));
        }
    }
    
    Edge &redge(Edge e) {
        if (e.from != e.to) return list[e.to][e.rev];
        else return list[e.to][e.rev+1];
    }
};

Graph G;

int dist[MAX_V];
int prevv[MAX_V];
int preve[MAX_V];

const ll INF = 1LL<<30;
int MinCost(Graph &G, int s, int t, int f) {
    int res = 0;
    while (f > 0) {
        fill(dist, dist+G.V, INF);
        dist[s] = 0;
        while (true) {
            bool update = false;
            for (int v = 0; v < G.V; ++v) {
                if (dist[v] == INF) continue;
                for (int i = 0; i < G[v].size(); ++i) {
                    Edge &e = G[v][i];
                    if (e.cap > 0 && dist[e.to] > dist[v] + e.cost) {
                        dist[e.to] = dist[v] + e.cost;
                        prevv[e.to] = v;
                        preve[e.to] = i;
                        update = true;
                    }
                }
            }
            if (!update) break;
        }
        
        if (dist[t] == INF) return -1;
        
        int d = f;
        for (int v = t; v != s; v = prevv[v]) {
            d = min(d, G[prevv[v]][preve[v]].cap);
        }
        f -= d;
        res += d * dist[t];
        for (int v = t; v != s; v = prevv[v]) {
            Edge &e = G[prevv[v]][preve[v]];
            Edge &re = G.redge(e);
            e.cap -= d;
            re.cap += d;
        }
    }
    return res;
}

int n;
int a, b;
vector<pint> block;
map<int,int> ind;

int main() {
    //freopen( "/Users/macuser/Documents/Programming/Contest/input.in", "r", stdin );
    
    while (cin >> n) {
        block.clear(); ind.clear();
        int id = 0;
        for (int i = 0; i < n; ++i) {
            cin >> a >> b;
            block.PB(MP(a,b));
            if (!ind.count(a)) {ind[a] = id; ++id;}
            if (!ind.count(b)) {ind[b] = id; ++id;}
        }
        int V = n + id + 2;
        int s = V-2, t = V-1;
        G.init(V);
        
        G.addedge(s, t, 1000000, 0);
        for (int i = 0; i < n; ++i) G.addedge(s, i, 1, 0);
        for (int i = 0; i < id; ++i) G.addedge(i+n, t, 1, 0);
        for (int i = 0; i < n; ++i) {
            int from = i;
            int to1 = ind[block[i].FI], to2 = ind[block[i].SE];
            G.addedge(from, to1+n, 1, -block[i].SE);
            if (to2 != to1) G.addedge(from, to2+n, 1, -block[i].FI);
        }
        //COUT(G);
        
        int res = MinCost(G, s, t, n);
        
        //COUT(G);
        
        cout << -res << endl;
    }
    
    return 0;
}
