分数: 700 点
问题陈述
我们有一个有向加权图 N 顶点。 每个顶点上面写有两个整数,Vertex上写的整数 i 是 A_i 和 B_i.
在此图中,有一条来自 Vertex 的边 x 到顶点 y 对于所有对 1 \leq x,y \leq N,其权重为 {\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