Dangerous Tower

Time limit2sMemory limit512 MB

Summary

Each block is 1 x Ai x Bi and can be placed with either Ai or Bi as its height; a block must be strictly narrower than the block below it. Maximize the total tower height.

Level: Medium6 of 10
Topics: Dynamic programming, Sorting, Binary search, Array
Solved: No attempts yet

Problem

Making good results at ICPC takes practice. The rabbit wants to win at ICPC, so it decided to practice again today.

Today's practice is stacking blocks carefully to gain enough dexterity to never mistype. Since there are plenty of blocks, let us build a tall tower.

There are N blocks, and the i-th block (1 ≤ i ≤ N) is a rectangular box of size 1 × A**i × B**i. The edge of length 1 is used in the depth direction, and the edges of lengths A**i and B**i are assigned one each to the horizontal direction and the height direction. When stacking blocks, the block on an upper level must be strictly shorter in horizontal length than the block on the level below it. Blocks may be used in any order, and some blocks may be left unused. Under these constraints, we want to build the tallest tower possible.

Input

N
A1 B1
 ...
AN BN

1 ≤ N ≤ 1,000, 1 ≤ A**i, B**i ≤ 1,000,000. All input values are integers.

Output

Print the maximum height of the tower on a single line.

Examples2

Example 1
Input
```
3
10 40
10 40
20 30
```
Expected output
```
80
```
Example 2
Input
```
4
1 2
2 3
3 4
4 1
```
Expected output
```
11
```