Rabbit 喜欢玩积木。她决定用 $N$ 个长方体积木搭建一座塔。第 $i$ 个积木的尺寸为 $1 \times A_i \times B_i$。她可以将该积木按以下方式之一放置：

• 深度 = 1，宽度 = $A_i$，高度 = $B_i$。
• 深度 = 1，宽度 = $B_i$，高度 = $A_i$。

塔被定义为一系列放置的积木 $p_1, \dots, p_k$，其中 $p_1$ 是最底部的积木，$p_k$ 是最顶部的积木。对于每个 $j$ ($1 \le j \le k - 1$)，$p_{j+1}$ 放置在 $p_j$ 之上，且 $p_{j+1}$ 的宽度必须严格小于 $p_j$ 的宽度。塔的高度是所有 $p_j$ 的高度之和，其中 $1 \le j \le k$。

Rabbit 可以按任意顺序使用她的积木。此外，她不必使用所有的积木。编写一个程序，求出她所能搭建的塔的最大可能高度。

输入格式

输入格式如下：

$N$ $A_1 \ B_1$ $\vdots$ $A_N \ B_N$

第一行包含一个整数 $N$ ($1 \le N \le 1000$)，表示积木的数量。接下来的 $N$ 行中，第 $i$ 行 ($1 \le i \le N$) 包含两个整数 $A_i$ 和 $B_i$ ($1 \le A_i \le 10^6, 1 \le B_i \le 10^6$)，表示第 $i$ 个积木的尺寸。

输出格式

你的程序应输出一个整数：塔的最大可能高度。

样例

样例输入 1

3
10 40
10 40
20 30

样例输出 1

80

样例输入 2

4
1 2
2 3
3 4
4 1

样例输出 2

11