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 <cmath>
#include <cstring>
#include <cstdlib>
#include <climits>
#include <ctime>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <unordered_map>
#include <complex>
#include <string>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <valarray>
#include <iterator>
using namespace std;
typedef long long int ll;
typedef unsigned int uint;
typedef unsigned char uchar;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)
#define ALL(container) container.begin(), container.end()
#define RALL(container) container.rbegin(), container.rend()
#define SZ(container) ((int)container.size())
#define mp(a,b) make_pair(a, b)
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {
os<<"["; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"]"; return os;
}
template<class T> ostream& operator<<(ostream &os, const set<T> &t) {
os<<"{"; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"}"; return os;
}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}

const int INF = 1<<28;
const double EPS = 1e-8;
const int MOD = 1000000007;


typedef int Weight;
struct Edge{
	int src,dst;
	Weight weight,cap; // weight が辺のコストを表す
	int rev; // 逆辺の番号
	Edge(int src,int dst,Weight weight=0,Weight cap=0,int rev=-1):
	src(src),dst(dst),weight(weight),cap(cap),rev(rev)
	{}
};
struct Node:public vector<Edge>{};
bool operator<(const Edge &a,const Edge &b){
	return a.weight<b.weight;
}
bool operator>(const Edge &a,const Edge &b){return b<a;}
typedef vector<Node> Graph;
typedef vector<vector<Weight> > Matrix;

//src から dst へ向かう容量 cap,コストcost の辺をグラフに追加する
void add_edge(Graph &G,int src,int dst,Weight cap,Weight cost){
	G[src].push_back(Edge(src,dst,cost,cap,G[dst].size()));
	G[dst].push_back(Edge(dst,src,-cost,0,G[src].size()-1));
}

Weight min_cost_flow(Graph &G,int s,int t,Weight f){
	typedef pair<Weight,int> P;
	Weight res=0;
	int V=G.size();
	vector<Weight> h(V,0);
	vector<int> prevv(V);
	vector<int> preve(V);
	if(s==t)return 0;
	bool start=true;
	while(f>0){
		vector<Weight> dist(V,INF);
		if(start){
			bool update=true;
			dist[s]=0;
			while(update){
				update=false;
				REP(v,V){
					if(dist[v]==INF)continue;
					REP(i,G[v].size()){
						Edge &e=G[v][i];
						if(e.cap>0&&dist[e.dst]>dist[v]+e.weight){
							dist[e.dst]=dist[v]+e.weight;
							prevv[e.dst]=v;
							preve[e.dst]=i;
							update=true;
						}
				}
			}
		}
		start=0;
		}else{
			priority_queue<P,vector<P>,greater<P> > que;
			dist[s]=0;
			que.push(P(0,s));
			while(!que.empty()){
				P p=que.top();que.pop();
				int v=p.second;
				if(dist[v]<p.first)continue;
				for(int i=0;i<(int)G[v].size();i++){
					Edge &e=G[v][i];
					if(e.cap>0&&dist[e.dst]>dist[v]+e.weight+h[v]-h[e.dst]){
						dist[e.dst]=dist[v]+e.weight+h[v]-h[e.dst];
						prevv[e.dst]=v;
						preve[e.dst]=i;
						que.push(P(dist[e.dst],e.dst));
					}
				}
			}
		}
		if(dist[t]==INF){
			return -1;
		}
		for(int v=0;v<V;v++)h[v]+=dist[v];
		Weight d=f;
		for(int v=t;v!=s;v=prevv[v]){
			d=min(d,G[prevv[v]][preve[v]].cap);
		}
		f-=d;
		res+=d*h[t];
		for(int v=t;v!=s;v=prevv[v]){
			Edge &e=G[prevv[v]][preve[v]];
			e.cap-=d;
			G[v][e.rev].cap+=d;
		}
	}
	return res;
}

int n;

int main(){
	scanf("%d\n", &n);
	vector<int> ItoP;
	vector<pii> bl;
	int sum = 0;
	REP(i, n){
		int a, b;
		scanf("%d%d", &a, &b);
		bl.emplace_back(a, b);
		ItoP.push_back(a);
		ItoP.push_back(b);
		sum += a+b;
	}
	sort(ALL(ItoP));
	UNIQUE(ItoP);
	int m = ItoP.size();
	unordered_map<int, int> PtoI;
	REP(i, m) PtoI[ItoP[i]] = i;
	Graph g(n+m+2);
	REP(i, n){
		add_edge(g, n+m, i, 1, 0);
		add_edge(g, i, n+PtoI[bl[i].first], 1, bl[i].first);
		add_edge(g, i, n+PtoI[bl[i].second], 1, bl[i].second);
		add_edge(g, i, n+m+1, 1, bl[i].first + bl[i].second);
	}
	REP(i, m) add_edge(g, n+i, n+m+1, 1, 0);
	cout << sum - min_cost_flow(g, n+m, n+m+1, n) << endl;
	return 0;
}