题目描述

$N$ 頂点の重み付き有向グラフがあります。 各頂点には $2$ つの整数が書かれており、頂点 $i$ には $A_i$ と $B_i$ が書かれています。

このグラフには、任意の $1\ \leq\ x,y\ \leq\ N$ について 頂点 $x$ から頂点 $y$ へ向かう辺があり、その重みは ${\rm\ min}(A_x,B_y)$ です。

このグラフの有向サイクルであって、すべての頂点をちょうど $1$ 度ずつ通るものを考えます。 そのようなサイクルの辺の重みの総和の最小値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

すべての頂点をちょうど $1$ 度ずつ通るサイクルの辺の重みの総和の最小値を出力せよ。

题目大意

• 给定一个 $n$ 边的有向完全图，每个点有两个点权 $a$ 和 $b$，一条边 $(u,v)$ 的边权值的计算方法为 $\min(a_u,b_v)$。
• 求边权和最小的哈密顿回路的边权和。
• 对于 $100\%$ 的数据，$2 \le n \le 10^5$，$1 \le a,b \le 10^9$。
• Translated by 一只书虫仔。

3
1 5
4 2
6 3

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

提示

制約

• $2\ \leq\ N\ \leq\ 10^5$
• $1\ \leq\ A_i\ \leq\ 10^9$
• $1\ \leq\ B_i\ \leq\ 10^9$
• 入力はすべて整数である。

Sample Explanation 1

頂点 $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$ になります。