#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <cassert>
#include <queue>
#include <functional>
#include <map>
using namespace std;
typedef long long ll;

const int MAX_V = 100010;
using Capacity = int;
using Cost = ll;
const auto inf = numeric_limits<Capacity>::max() / 8;

struct Edge {
	int dst;
	Capacity cap, cap_orig;
	Cost cost;
	int revEdge; bool isRev;
	Edge(int dst, Capacity cap, Cost cost, int revEdge, bool isRev)
		:dst(dst), cap(cap), cap_orig(cap), cost(cost), revEdge(revEdge), isRev(isRev) {
	}
};

struct PrimalDual {
	int n;
	vector<vector<Edge> > g;
	PrimalDual(int n_) : n(n_), g(vector<vector<Edge> >(n_)) {}
	void add_edge(int src, int dst, Capacity cap, Cost cost) { // テヲツ慊嘉・ツ青妥ィツセツコ
		g[src].emplace_back(dst, cap, cost, g[dst].size(), false);
		g[dst].emplace_back(src, 0, -cost, g[src].size() - 1, true);
	}
	Cost solve(int s, int t, int f) {
		Cost res = 0;
		static Cost h[MAX_V], dist[MAX_V];
		static int prevv[MAX_V], preve[MAX_V];
		for(int i = 0; i < n; i++) {
			h[i] = 0;
		}
		while(f > 0) {
			typedef pair<Cost, int> pcv;
			priority_queue<pcv, vector<pcv>, greater<pcv> > q;
			for(int i = 0; i < n; i++) {
				dist[i] = inf;
			}
			dist[s] = 0;
			q.emplace(pcv(0, s));
			while(q.size()) {
				pcv p = q.top(); q.pop();
				int v = p.second;
				if(dist[v] < p.first) continue;
				for(int i = 0; i < g[v].size(); i++) {
					Edge &e = g[v][i];
					if(e.cap > 0 && dist[e.dst] > dist[v] + e.cost + h[v] - h[e.dst]) {
						dist[e.dst] = dist[v] + e.cost + h[v] - h[e.dst];
						prevv[e.dst] = v;
						preve[e.dst] = i;
						q.emplace(pcv(dist[e.dst], e.dst));
					}
				}
			}
			if(dist[t] == inf) {
				return -1;
			}
			for(int v = 0; v < n; v++) {
				h[v] += dist[v];
			}
			// s-t テゥツ鳴禿ヲツ慊?ァツ淞ュティツキツッテ」ツ?ォテヲツイツソテ」ツ?」テ」ツ?ヲテァツ崢ョテ、ツクツ?ヲツ敖ッテヲツオツ?」ツ??
			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.revEdge].cap += d;
			}
		}
		return res;
	}
	// テヲツオツ?」ツつ古」ツ?淌」ツδ陛」ツδュテ」ツδシ=テ・ツ?ε」ツ??」ツ?ョテ・ツョツケテゥツ??テァツ渉セテ・ツ慊ィテ」ツ?ョテ・ツョツケテゥツ?湘」ツつ津ィツ。ツィテァツ、ツコ
	void view() {
		for(int i = 0; i < g.size(); i++) {
			for(int j = 0; j < g[i].size(); j++) {
				if(!g[i][j].isRev) {
					Edge& e = g[i][j];
					printf("%3d->%3d (flow:%d)\n", i, e.dst, e.cap_orig - e.cap);
				}
			}
		}
	}
};

ll A[1000];
ll B[1000];

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;

	map<ll, int> idx_map;
	for(int i = 0; i < N; i++) {
		cin >> A[i] >> B[i];
		idx_map[A[i]] = -1;
		idx_map[B[i]] = -1;
	}

	int M = 0;
	for(auto&& p : idx_map) {
		idx_map[p.first] = M++;
	}

	PrimalDual pd(N + M + 3);
	int S = N + M, T = N + M + 1, D = N + M + 2;
	for(int i = 0; i < N; i++) {
		pd.add_edge(S, i, 1, 0);
		pd.add_edge(i, N + idx_map[A[i]], 1, -B[i]);
		pd.add_edge(i, N + idx_map[B[i]], 1, -A[i]);
	}
	for(int i = 0; i < M; i++) {
		pd.add_edge(N + i, T, 1, 0);
	}
	pd.add_edge(S, T, M, 0);

	//pd.view();
	cout << -pd.solve(S, T, M) << endl;
}
### Prompt

Please provide a cpp coded solution to the problem described below:

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

### Response

```cpp
#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <cassert>
#include <queue>
#include <functional>
#include <map>
using namespace std;
typedef long long ll;

const int MAX_V = 100010;
using Capacity = int;
using Cost = ll;
const auto inf = numeric_limits<Capacity>::max() / 8;

struct Edge {
	int dst;
	Capacity cap, cap_orig;
	Cost cost;
	int revEdge; bool isRev;
	Edge(int dst, Capacity cap, Cost cost, int revEdge, bool isRev)
		:dst(dst), cap(cap), cap_orig(cap), cost(cost), revEdge(revEdge), isRev(isRev) {
	}
};

struct PrimalDual {
	int n;
	vector<vector<Edge> > g;
	PrimalDual(int n_) : n(n_), g(vector<vector<Edge> >(n_)) {}
	void add_edge(int src, int dst, Capacity cap, Cost cost) { // テヲツ慊嘉・ツ青妥ィツセツコ
		g[src].emplace_back(dst, cap, cost, g[dst].size(), false);
		g[dst].emplace_back(src, 0, -cost, g[src].size() - 1, true);
	}
	Cost solve(int s, int t, int f) {
		Cost res = 0;
		static Cost h[MAX_V], dist[MAX_V];
		static int prevv[MAX_V], preve[MAX_V];
		for(int i = 0; i < n; i++) {
			h[i] = 0;
		}
		while(f > 0) {
			typedef pair<Cost, int> pcv;
			priority_queue<pcv, vector<pcv>, greater<pcv> > q;
			for(int i = 0; i < n; i++) {
				dist[i] = inf;
			}
			dist[s] = 0;
			q.emplace(pcv(0, s));
			while(q.size()) {
				pcv p = q.top(); q.pop();
				int v = p.second;
				if(dist[v] < p.first) continue;
				for(int i = 0; i < g[v].size(); i++) {
					Edge &e = g[v][i];
					if(e.cap > 0 && dist[e.dst] > dist[v] + e.cost + h[v] - h[e.dst]) {
						dist[e.dst] = dist[v] + e.cost + h[v] - h[e.dst];
						prevv[e.dst] = v;
						preve[e.dst] = i;
						q.emplace(pcv(dist[e.dst], e.dst));
					}
				}
			}
			if(dist[t] == inf) {
				return -1;
			}
			for(int v = 0; v < n; v++) {
				h[v] += dist[v];
			}
			// s-t テゥツ鳴禿ヲツ慊?ァツ淞ュティツキツッテ」ツ?ォテヲツイツソテ」ツ?」テ」ツ?ヲテァツ崢ョテ、ツクツ?ヲツ敖ッテヲツオツ?」ツ??
			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.revEdge].cap += d;
			}
		}
		return res;
	}
	// テヲツオツ?」ツつ古」ツ?淌」ツδ陛」ツδュテ」ツδシ=テ・ツ?ε」ツ??」ツ?ョテ・ツョツケテゥツ??テァツ渉セテ・ツ慊ィテ」ツ?ョテ・ツョツケテゥツ?湘」ツつ津ィツ。ツィテァツ、ツコ
	void view() {
		for(int i = 0; i < g.size(); i++) {
			for(int j = 0; j < g[i].size(); j++) {
				if(!g[i][j].isRev) {
					Edge& e = g[i][j];
					printf("%3d->%3d (flow:%d)\n", i, e.dst, e.cap_orig - e.cap);
				}
			}
		}
	}
};

ll A[1000];
ll B[1000];

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;

	map<ll, int> idx_map;
	for(int i = 0; i < N; i++) {
		cin >> A[i] >> B[i];
		idx_map[A[i]] = -1;
		idx_map[B[i]] = -1;
	}

	int M = 0;
	for(auto&& p : idx_map) {
		idx_map[p.first] = M++;
	}

	PrimalDual pd(N + M + 3);
	int S = N + M, T = N + M + 1, D = N + M + 2;
	for(int i = 0; i < N; i++) {
		pd.add_edge(S, i, 1, 0);
		pd.add_edge(i, N + idx_map[A[i]], 1, -B[i]);
		pd.add_edge(i, N + idx_map[B[i]], 1, -A[i]);
	}
	for(int i = 0; i < M; i++) {
		pd.add_edge(N + i, T, 1, 0);
	}
	pd.add_edge(S, T, M, 0);

	//pd.view();
	cout << -pd.solve(S, T, M) << endl;
}
```