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 <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 4000
typedef pair<int,int> P;

struct Edge{
	Edge(int arg_to,int arg_capacity,int arg_cost,int arg_rev_index){
		to = arg_to;
		capacity = arg_capacity;
		cost = arg_cost;
		rev_index = arg_rev_index;
	}

	int to,capacity,cost,rev_index;
};

struct Info{
	int A,B;
};

int V;
int value_index[2000],wood_index[1000];
vector<Edge> G[NUM];
int dist[NUM];
int pre_node[NUM],pre_edge[NUM];
Info info[1000];
int h[NUM];


void add_edge(int from,int to,int capacity,int cost){
	G[from].push_back(Edge(to,capacity,cost,G[to].size()));
	G[to].push_back(Edge(from,0,-cost,G[from].size()-1));
}

int min_cost_flow(int source,int sink,int flow){
	int ret = 0;
	for(int i = 0; i < V; i++)h[i] = 0;
	while(flow > 0){
		priority_queue<P,vector<P>,greater<P>> Q;
		for(int i = 0; i < V; i++)dist[i] = BIG_NUM;
		dist[source] = 0;
		Q.push(P(0,source));

		while(!Q.empty()){
			P p = Q.top();
			Q.pop();
			int node_id = p.second;
			if(dist[node_id] < p.first)continue;
			for(int i = 0; i < G[node_id].size(); i++){
				Edge &e = G[node_id][i];
				if(e.capacity > 0 && dist[e.to] > dist[node_id]+e.cost+h[node_id]-h[e.to]){
					dist[e.to] = dist[node_id]+e.cost+h[node_id]-h[e.to];
					pre_node[e.to] = node_id;
					pre_edge[e.to] = i;
					Q.push(P(dist[e.to],e.to));
				}
			}
		}

		if(dist[sink] == BIG_NUM){
			return -1;
		}

		for(int node_id = 0; node_id < V; node_id++)h[node_id] += dist[node_id];

		int tmp_flow = flow;
		for(int node_id = sink; node_id != source; node_id = pre_node[node_id]){
			tmp_flow = min(tmp_flow,G[pre_node[node_id]][pre_edge[node_id]].capacity);
		}
		flow -= tmp_flow;
		ret += tmp_flow*h[sink];
		for(int node_id = sink; node_id != source; node_id = pre_node[node_id]){
			Edge &e = G[pre_node[node_id]][pre_edge[node_id]];
			e.capacity -= tmp_flow;
			G[node_id][e.rev_index].capacity += tmp_flow;
		}
	}
	return ret;
}

int main(){

	int N;
	scanf("%d",&N);

	vector<int> VALUE;

	int source = 0,sink = 1,index = 2;

	for(int i = 0; i < N; i++){
		scanf("%d %d",&info[i].A,&info[i].B);
		VALUE.push_back(info[i].A);
		VALUE.push_back(info[i].B);
	}

	sort(VALUE.begin(),VALUE.end());
	VALUE.erase(unique(VALUE.begin(),VALUE.end()),VALUE.end());

	for(int i = 0; i < VALUE.size(); i++){
		value_index[i] = index++;
		add_edge(source,value_index[i],1,0);
	}

	for(int i = 0; i < N; i++){
		wood_index[i] = index++;
		add_edge(wood_index[i],sink,1,0);
	}

	for(int i = 0; i < VALUE.size(); i++){
		for(int k = 0; k < N; k++){
			if(info[k].A == VALUE[i]){
				add_edge(value_index[i],wood_index[k],1,-info[k].B);
			}
			if(info[k].B == VALUE[i]){
				add_edge(value_index[i],wood_index[k],1,-info[k].A);
			}
		}
	}

	add_edge(source,sink,2010,0);

	V = index;

	printf("%d\n", -min_cost_flow(source,sink,2010));

	return 0;
}

