AT_arc164_c [ARC164C] Reversible Card Game

[problemUrl]: https://atcoder.jp/contests/arc164/tasks/arc164_c 両面に数が書かれた $ N $ 枚のカードがあり、$ i $ 枚目のカードには片方の面に赤い数字で $ A_i $ が、もう片方の面には青い数字で $ B_i $ が書かれています。初め、全てのカードは赤い数字が書かれた面を表にして置かれており、Alice と Bob は次のような手順を繰り返すゲームをします。 - まず、Alice が残っているカードの中から $ 1 $ 枚を選び、裏返す。次に、Bob が残っているカードの中から $ 1 $ 枚を取り除く。このとき、取り除いたカードの表側の面に書かれていた数の分だけ Bob は得点を得る。 残っているカードが $ 0 $ 枚になった時、ゲームを終了します。 Alice はゲーム終了時の Bob の得点を最小にしようとし、Bob はこれを最大にしようとします。両者が最善の手順を取ったとき、ゲーム終了時の Bob の得点は何点でしょうか。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ \vdots $ $ A_N $ $ B_N $

答えを整数で出力せよ。

### 制約 - $ 1\leq\ N\leq\ 2\times\ 10^5 $ - $ 1\leq\ A_i,\ B_i\leq\ 10^9 $ $ (1\leq\ i\ \leq\ N) $ - 入力される値はすべて整数である ### Sample Explanation 1 初めの状態では、表側の面に書かれた数はそれぞれ $ 6,2,5 $ です。ここから、例えば次のような進行が考えられます。 1. Alice は $ 1 $ 枚目のカードを裏返す。このとき、表側の面に書かれた数は $ 4,2,5 $ となる。Bob は $ 3 $ 枚目のカードを取り除き、$ 5 $ 点を得る。 2. Alice は $ 2 $ 枚目のカードを裏返す。このとき、表側の面に書かれた数は $ 4,1 $ となる。Bob は $ 2 $ 枚目のカードを取り除き、$ 1 $ 点を得る。 3. Alice は最後に残った $ 1 $ 枚目のカードを裏返す。このとき、表側の面に書かれた数は $ 6 $ となる。Bob はこれを取り除き、$ 6 $ 点を得る。 この場合、Bob が最終的に得る得点は $ 12 $ 点です。実は、この進行は双方の最善手の一例であり、答えは $ 12 $ となります。