AT_agc028_c [AGC028C] Min Cost Cycle

[problemUrl]: https://atcoder.jp/contests/agc028/tasks/agc028_c $ N $ 頂点の重み付き有向グラフがあります。 各頂点には $ 2 $ つの整数が書かれており、頂点 $ i $ には $ A_i $ と $ B_i $ が書かれています。 このグラフには、任意の $ 1\ \leq\ x,y\ \leq\ N $ について 頂点 $ x $ から頂点 $ y $ へ向かう辺があり、その重みは $ {\rm\ min}(A_x,B_y) $ です。 このグラフの有向サイクルであって、すべての頂点をちょうど $ 1 $ 度ずつ通るものを考えます。 そのようなサイクルの辺の重みの総和の最小値を求めてください。

N/A

N/A

### 制約 - $ 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 $ になります。