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"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class T>
using Table = vector<vector<T>>;
const ld eps=1e-9;

// < "D:\D_Download\Visual Studio 2015\Projects\programing_contest_c++\Debug\a.txt"

struct Compress {
	map<int, int>mp;
	map<int, int>revmp;

	Compress(vector<int>vs) {
		sort(vs.begin(), vs.end());
		vs.erase(unique(vs.begin(), vs.end()), vs.end());
		for (int i = 0; i < vs.size(); ++i) {
			mp[vs[i]] = i;
			revmp[i] = vs[i];
		}
	}
};
typedef long long  Weight;
struct Edge {
	int src, dest;
	int cap, rev;
	Weight weight;
	bool operator < (const Edge &rhs) const { return weight > rhs.weight; }
};

const int V = 4000;
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
typedef vector<Weight> Array;
typedef vector<Array> Matrix;
Weight h[V];                //??????????????£???
Weight dist[V];             //???????????¢
int prevv[V], preve[V];  //??´???????????¨??????

void add_edge(Graph &g, int src, int dest, int cap, int weight) {
	g[src].push_back(Edge { src, dest, cap, (int)g[dest].size(), weight });
	g[dest].push_back(Edge { dest, src, 0, (int)g[src].size() - 1, -weight });
}
#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(auto i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
const int INF = 2147483647;
const long long int L_INF = 9223372036854775807;
Weight min_cost_flow(Graph &g, int s, int t, int f) {
	Weight res = 0;
	memset(h, 0, sizeof(h));
	typedef pair<Weight, int> P;
	while (f > 0) {
		priority_queue<P, vector<P>, greater<P> > que;
		fill(dist, dist + V, INF);
		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;
			REP(i, g[v].size()) {
				Edge &e = g[v][i];
				if (e.cap > 0 && dist[e.dest] > dist[v] + e.weight + h[v] - h[e.dest]) {
					dist[e.dest] = dist[v] + e.weight + h[v] - h[e.dest];
					prevv[e.dest] = v;
					preve[e.dest] = i;
					que.push(P(dist[e.dest], e.dest));
				}
			}
		}
		if (dist[t] == INF) return -1;
		REP(v, V) h[v] += dist[v];

		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 * 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 main() {
	int N; cin >> N;
	vector<int>vs;
	vector<pair<long long int,long long  int>>ps;
	for (int i = 0; i < N; ++i) {
		long long int a, b; cin >> a >> b;
		ps.emplace_back(a, b);
		vs.push_back(a);
		vs.push_back(b);
	}
	Compress cp(vs);

	const int start = 0;
	const int snode = start + 1;
	const int he = snode + N;
	const int goal = he + 2*N;
	Graph g(goal+1);
	for (int i = 0; i < N; ++i) {
		add_edge(g,start, snode + i, 1, 0);
	}
	for (int i = 0; i < N; ++i) {
		add_edge(g, snode+i, he + cp.mp[ps[i].second], 1, 1000000 - ps[i].first);
		add_edge(g, snode + i, he + cp.mp[ps[i].first], 1, 1000000 - ps[i].second);
		add_edge(g, snode + i, goal, 1, 1000000);
	}
	for (int i = 0; i < 2*N; ++i) {
		add_edge(g, he + i, goal, 1, 0);
	}
	auto p = min_cost_flow(g, start, goal,N);
	long long int ans = 1000000 * N - p;
	cout << ans << endl;
	return 0;
}