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>
using namespace std;

#define rep(i,x,y) for(int i=(x);i<(y);++i)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif

const int inf=1e9;
const int64_t inf64=1e18;
const double eps=1e-9;

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
    	os << v << ",";
    }
    os << "]";
    return os;
}

template<class flow_type,class cost_type> struct min_cost_flow{
    struct edge{
        int to,from,rev;
        flow_type cap;
        cost_type cost;
        edge(int to,int from,int rev,flow_type cap,cost_type cost):
            to(to),from(from),rev(rev),cap(cap),cost(cost){}
    };
    const int size=0;
    vector<vector<edge>> graph;
    min_cost_flow(int size_):size(size_),graph(size_){}
    void add_edge(int from,int to,flow_type cap,cost_type cost){
        graph[from].push_back(edge(to,from,int(graph[to].size()),cap,cost));
        graph[to].push_back(edge(from,to,int(graph[from].size()-1),0,-cost));
    }
    cost_type min_path(int s,int t){
        const cost_type inf=numeric_limits<cost_type>::max();
        vector<cost_type> dist(size,inf);
        vector<edge*> route(size);
        queue<int> que;
        vector<bool> inq(size);
        dist[s]=0;
        que.push(s);
        inq[s]=true;
        while(!que.empty()){
            int u=que.front();
            que.pop();
            inq[u]=false;
            for(edge &e:graph[u]){
                if(e.cap==0) continue;
                int v=e.to;
                if(dist[v]>dist[u]+e.cost){
                    dist[v]=dist[u]+e.cost;
                    route[v]=&e;
                    if(!inq[v]){
                        que.push(v);
                        inq[v]=true;
                    }
                }
            }
        }

        if(dist[t]==inf) return inf;
        flow_type flow=numeric_limits<flow_type>::max();
        {
            int v=t;
            while(v!=s){
                edge &e=*route[v];
                //e.cap-=1;
                //graph[e.to][e.rev].cap+=1;
                //c+=e.cost;
                flow=min(flow,e.cap);
                v=e.from;
            }
        }
        cost_type c=0;
        {
            int v=t;
            while(v!=s){
                edge &e=*route[v];
                e.cap-=flow;
                graph[e.to][e.rev].cap+=flow;
                c+=e.cost*flow;
                v=e.from;
            }
        }
        return dist[t];
    }
    cost_type calc_min_cost_flow(int s,int t,flow_type flow){
        cost_type total_cost=0;
        for(flow_type i=0; i<flow; ++i){
            cost_type c=min_path(s,t);
            if(c==numeric_limits<cost_type>::max()) return c;
            total_cost+=c;
        }
        return total_cost;
    }
};


void solve(){
    int n;
    cin >> n;
    min_cost_flow<int,int> mcf(4096);
    const int s=4094,t=4095;
    rep(i,0,n){
        mcf.add_edge(s,i,1,0);
        mcf.add_edge(i,4093,1,0);
    }

    vector<int> a(n),b(n),index(1000001),value;
    rep(i,0,n){
        cin >> a[i] >> b[i];
        value.push_back(a[i]);
        value.push_back(b[i]);
    }
    sort(value.begin(),value.end());
    value.erase(unique(value.begin(),value.end()),value.end());

    rep(i,0,value.size()){
        index[value[i]]=i+n;
        mcf.add_edge(index[value[i]],t,1,0);
    }
    mcf.add_edge(4093,t,inf,0);
    rep(i,0,n){
        mcf.add_edge(i,index[a[i]],1,-b[i]);
        mcf.add_edge(i,index[b[i]],1,-a[i]);
    }
    cout << -mcf.calc_min_cost_flow(s,t,n) << endl;
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(10);
    solve();
    return 0;
}