#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
typedef long double ld;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<ld, ld> LDP;
typedef complex<ld> Point;
const ll mod = 1000000007;
const ll INF = mod * mod;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)

int max_n;
const int mn = 100000;
struct edge {
	int to, cap, cost, rev;
};
vector<edge> G[mn];
int par[mn];
int dist[mn];
void add_edge(int from, int to, int cap, int cost) {
	G[from].push_back({ to,cap,cost,(int)G[to].size() });
	G[to].push_back({ from,0,-cost,(int)G[from].size() - 1 });
	max_n = max({ max_n, from + 1, to + 1 });
}
int minimum_road(int s, int t) {
	fill(par, par + max_n, -1);
	fill(dist, dist + max_n, mod);
	dist[s] = 0;
	priority_queue<P, vector<P>, greater<P>> q; q.push({ 0,s });
	while (!q.empty()) {
		P p = q.top(); q.pop();
		int id = p.second;
		if (id == t)continue;
		rep(j, G[id].size()) {
			if (G[id][j].cap > 0) {
				int to = G[id][j].to;
				int nd = p.first + G[id][j].cost;
				if (nd < dist[to]) {
					dist[to] = nd;
					par[to] = id;
					q.push({ dist[to],to });
				}
			}
		}
	}
	int cur = t;
	while (cur != s) {
		int p = par[cur];
		if (p < 0)return -1;
		rep(j, G[p].size()) {
			if (G[p][j].cap > 0 && G[p][j].to == cur && dist[p] + G[p][j].cost == dist[cur]) {
				G[p][j].cap--;
				G[cur][G[p][j].rev].cap++;
				break;
			}
		}
		cur = p;
	}
	return dist[t];
}
int minimum_cost_flow(int s, int t) {
	int ret = 0;
	while(true) {
		int z = minimum_road(s, t);
		if (z < 0)break;
		ret += z;
	}
	return ret;
}

int x[1000], y[1000];
void solve() {
	int n; cin >> n;
	int ans = 0;
	vector<int> v;
	rep(i, n) {
		cin >> x[i] >> y[i];
		ans += x[i] + y[i];
		v.push_back(x[i]);
		v.push_back(y[i]);
	}
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	map<int, int> mp;
	rep(i, v.size()) {
		mp[v[i]] = i;
	}
	int s = 4 * n; int t = s + 1;
	rep(i, v.size()) {
		add_edge(s, i, 1, 0);
	}
	rep(i, n) {
		int idx = mp[x[i]];
		int idy = mp[y[i]];
		int id = i + v.size();
		add_edge(id, t, 1, 0);
		add_edge(s, id, 1, x[i] + y[i]);
		add_edge(idx, id, 1, x[i]);
		add_edge(idy, id, 1, y[i]);
	}
	ans -= minimum_cost_flow(s, t);
	cout << ans << endl;
}
int main() {
	solve();
	//stop
	return 0;
}


### Prompt

Generate a CPP solution to the following problem:

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<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
typedef long double ld;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<ld, ld> LDP;
typedef complex<ld> Point;
const ll mod = 1000000007;
const ll INF = mod * mod;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)

int max_n;
const int mn = 100000;
struct edge {
	int to, cap, cost, rev;
};
vector<edge> G[mn];
int par[mn];
int dist[mn];
void add_edge(int from, int to, int cap, int cost) {
	G[from].push_back({ to,cap,cost,(int)G[to].size() });
	G[to].push_back({ from,0,-cost,(int)G[from].size() - 1 });
	max_n = max({ max_n, from + 1, to + 1 });
}
int minimum_road(int s, int t) {
	fill(par, par + max_n, -1);
	fill(dist, dist + max_n, mod);
	dist[s] = 0;
	priority_queue<P, vector<P>, greater<P>> q; q.push({ 0,s });
	while (!q.empty()) {
		P p = q.top(); q.pop();
		int id = p.second;
		if (id == t)continue;
		rep(j, G[id].size()) {
			if (G[id][j].cap > 0) {
				int to = G[id][j].to;
				int nd = p.first + G[id][j].cost;
				if (nd < dist[to]) {
					dist[to] = nd;
					par[to] = id;
					q.push({ dist[to],to });
				}
			}
		}
	}
	int cur = t;
	while (cur != s) {
		int p = par[cur];
		if (p < 0)return -1;
		rep(j, G[p].size()) {
			if (G[p][j].cap > 0 && G[p][j].to == cur && dist[p] + G[p][j].cost == dist[cur]) {
				G[p][j].cap--;
				G[cur][G[p][j].rev].cap++;
				break;
			}
		}
		cur = p;
	}
	return dist[t];
}
int minimum_cost_flow(int s, int t) {
	int ret = 0;
	while(true) {
		int z = minimum_road(s, t);
		if (z < 0)break;
		ret += z;
	}
	return ret;
}

int x[1000], y[1000];
void solve() {
	int n; cin >> n;
	int ans = 0;
	vector<int> v;
	rep(i, n) {
		cin >> x[i] >> y[i];
		ans += x[i] + y[i];
		v.push_back(x[i]);
		v.push_back(y[i]);
	}
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	map<int, int> mp;
	rep(i, v.size()) {
		mp[v[i]] = i;
	}
	int s = 4 * n; int t = s + 1;
	rep(i, v.size()) {
		add_edge(s, i, 1, 0);
	}
	rep(i, n) {
		int idx = mp[x[i]];
		int idy = mp[y[i]];
		int id = i + v.size();
		add_edge(id, t, 1, 0);
		add_edge(s, id, 1, x[i] + y[i]);
		add_edge(idx, id, 1, x[i]);
		add_edge(idy, id, 1, y[i]);
	}
	ans -= minimum_cost_flow(s, t);
	cout << ans << endl;
}
int main() {
	solve();
	//stop
	return 0;
}


```