问题描述

我们有一个有向加权图，其中有 $N$ 个顶点。每个顶点上都有两个整数，顶点 $i$ 上的整数是 $A_i$ 和 $B_i$。

在这个图中，对于所有的顶点对 $1 \\leq x,y \\leq N$，从顶点 $x$ 到顶点 $y$ 有一条边，其权重为 ${\\rm min}(A_x,B_y)$。

我们将考虑在这个图中遍历每个顶点一次的有向循环。找到这样一个循环中边的最小总权重。

约束条件

• $2 \\leq N \\leq 10^5$
• $1 \\leq A_i \\leq 10^9$
• $1 \\leq B_i \\leq 10^9$
• 输入数据中的所有值均为整数。

输入

从标准输入读入输入数据，输入格式如下：

$N$ $A_1$ $B_1$ $A_2$ $B_2$ $:$ $A_N$ $B_N$

输出

打印出在这样一个循环中边的最小总权重。

示例输入1

3
1 5
4 2
6 3

示例输出1

7

考虑循环 $1→3→2→1$。这些边的权重分别是 ${\\rm min}(A_1,B_3)=1$，${\\rm min}(A_3,B_2)=2$ 和 ${\\rm min}(A_2,B_1)=4$，总共为 $7$。由于没有总权重小于 $7$ 的循环，答案为 $7$。

示例输入2

4
1 5
2 6
3 7
4 8

示例输出2

10

示例输入3

6
19 92
64 64
78 48
57 33
73 6
95 73

示例输出3

227