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 <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> ipair;
typedef tuple<int, int, int> ituple;

const ll INF = LLONG_MAX;
// const int MOD = (int)1e9 + 7;
// const double EPS = 1e-10;
#define PI acosl(-1)
#define MAX_N 100 + 2

/**
 * 最小費用流
 */
class MinCostFlow{
  struct edge{
    int to, cap, cost, rev;
  };

protected:
  static const int MAX_V = 10000 + 5;
  int V; // 頂点数
  vector<edge> G[MAX_V]; // グラフの隣接リスト表現
  ll dist[MAX_V]; // 最短距離
  int prevV[MAX_V], prevE[MAX_V]; // 直前の頂点と辺

public:
  MinCostFlow(){}
  MinCostFlow(int v){
    assert(v <= MAX_V);
    V = v;
  }
  void addEdge(int from, int to, int cap, int cost){
    G[from].push_back((edge){to, cap, cost, (int)G[to].size()});
    G[to].push_back((edge){from, 0, -cost, (int)G[from].size() - 1});
  }

  // sからtへの最小費用流を求める
  int exec(int s, int t, int f){
    int res = 0;

    while (f > 0){
      // ベルマンフォード法により、s-t間の最短経路を求める
      fill(dist, dist + V, INF);
      dist[s] = 0;
      bool update = true;
      while(update){
        update = false;
        for (int v = 0; v < V; v++){
          if (dist[v] == INF){
            continue;
          }

          for (int i = 0; i < G[v].size(); i++){
            edge &e = G[v][i];
            if (e.cap > 0 && dist[e.to] > dist[v] + e.cost){
              dist[e.to] = dist[v] + e.cost;
              prevV[e.to] = v;
              prevE[e.to] = i;
              update = true;
            }
          }

        }
      }

      if (dist[t] == INF){
        // これ以上流せない
        return -1;
      }

      // 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 * dist[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;
  }
};

#define MAX_LENGTH 1000000
#define LENGTH_NODE_INIT 0
const int SOURCE_NODE = 0, SINK_NODE = 1;
VI froms, tos, caps, costs;
int length_node[MAX_LENGTH + 2];

// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_B
void exec(){
  int n, length[2], v = 2;
  cin >> n;

  for (int i = 0; i < n; i++){
    scanf("%d%d", &length[0], &length[1]);

    int entrance = v++;

    // source -> entrance
    froms.push_back(SOURCE_NODE);
    tos.push_back(entrance);
    caps.push_back(1);
    costs.push_back(0);

    // entrance -> 0
    int zero = v++;
    froms.push_back(entrance);
    tos.push_back(zero);
    caps.push_back(1);
    costs.push_back(0);

    // 0 -> sink
    froms.push_back(zero);
    tos.push_back(SINK_NODE);
    caps.push_back(1);
    costs.push_back(0);

    for (int j = 0; j <= 1; j++){
      int a = length[j];
      int len_cost = length[1 - j];

      // entrance -> A
      int node_a = v++;
      froms.push_back(entrance);
      tos.push_back(node_a);
      caps.push_back(1);
      costs.push_back(0);

      if (length_node[len_cost] == LENGTH_NODE_INIT) {
        int l_node = v++;

        // A -> length_node.A
        froms.push_back(node_a);
        tos.push_back(l_node);
        caps.push_back(1);
        costs.push_back(-a);

        // length_node.A -> sink
        froms.push_back(l_node);
        tos.push_back(SINK_NODE);
        caps.push_back(1);
        costs.push_back(0);

        length_node[len_cost] = l_node;
      }
      else {
        // A -> length_node.A
        froms.push_back(node_a);
        tos.push_back(length_node[len_cost]);
        caps.push_back(1);
        costs.push_back(-a);
      }

    }

  }

  MinCostFlow mcf = MinCostFlow(v);

  for (int i = 0; i < froms.size(); i++){
    mcf.addEdge(froms[i], tos[i], caps[i], costs[i]);
  }

  cout << -mcf.exec(SOURCE_NODE, SINK_NODE, n) << endl;
}

void solve(){
  int t = 1;
  // scanf("%d", &t);
  for (int i = 0; i < t; i++){
    exec();
  }
}

int main(){
  solve();
  return 0;
}

