得分 : $700$ 分

问题陈述

我们有一个包含 $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$

输出

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

3
1 5
4 2
6 3

7

考虑环 $1 \to 3 \to 2 \to 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$。

4
1 5
2 6
3 7
4 8

10

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

227