题目描述

有一个包含 $N$ 个顶点的带权有向图。每个顶点上写有两个整数，对于顶点 $i$，写有 $A_i$ 和 $B_i$。

在这个图中，对于任意的 $1 \leq x, y \leq N$，都存在一条从顶点 $x$ 指向顶点 $y$ 的有向边，其权值为 $\min(A_x, B_y)$。

请考虑经过所有顶点恰好一次的有向环（即哈密顿回路）。请你求出所有这样的环中，边权和的最小值。

输入格式

输入以如下格式从标准输入读入：

$N$ $A_1$ $B_1$ $A_2$ $B_2$ $\cdots$ $A_N$ $B_N$

输出格式

请输出经过所有顶点恰好一次的有向环的边权和的最小值。

样例 1

输入

3
1 5
4 2
6 3

输出

7

样例 2

输入

4
1 5
2 6
3 7
4 8

输出

10

样例 3

输入

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

输出

227

说明/提示

限制条件

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

样例解释 1

考虑经过顶点 $1 \to 3 \to 2 \to 1$ 的环，其边权分别为 $\min(A_1, B_3)=1$，$\min(A_3, B_2)=2$，$\min(A_2, B_1)=4$，总和为 $7$。无法得到比 $7$ 更小的边权和，因此答案为 $7$。

由 ChatGPT 4.1 翻译