C - Reversible Card Game Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

両面に数が書かれた N 枚のカードがあり、i 枚目のカードには片方の面に赤い数字で A_i が、もう片方の面には青い数字で B_i が書かれています。初め、全てのカードは赤い数字が書かれた面を表にして置かれており、Alice と Bob は次のような手順を繰り返すゲームをします。

  • まず、Alice が残っているカードの中から 1 枚を選び、裏返す。次に、Bob が残っているカードの中から 1 枚を取り除く。このとき、取り除いたカードの表側の面に書かれていた数の分だけ Bob は得点を得る。

残っているカードが 0 枚になった時、ゲームを終了します。

Alice はゲーム終了時の Bob の得点を最小にしようとし、Bob はこれを最大にしようとします。両者が最善の手順を取ったとき、ゲーム終了時の Bob の得点は何点でしょうか。

制約

  • 1\leq N\leq 2\times 10^5
  • 1\leq A_i, B_i\leq 10^9 (1\leq i \leq N)
  • 入力される値はすべて整数である

入力

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

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N

出力

答えを整数で出力せよ。

入力例 1

3
6 4
2 1
5 3

出力例 1

12

初めの状態では、表側の面に書かれた数はそれぞれ 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 となります。

入力例 2

5
166971716 552987438
219878198 619875818
918378176 518975015
610749017 285601372
701849287 307601390

出力例 2

3078692091

Score : 500 points

Problem Statement

There are N cards, each with a number written on both sides. On the i-th card, the number A_i is written in red on one side, and the number B_i is written in blue on the other side. Initially, all cards are placed with the red number side facing up. Alice and Bob play a game in which they repeat the following steps.

  • First, Alice chooses one of the remaining cards and flips it over. Next, Bob removes one of the remaining cards. Then, Bob scores points equal to the number written on the face-up side of the removed card.

The game ends when there are no cards left.

Alice tries to minimize Bob's score at the end of the game, and Bob tries to maximize it. What is Bob's score at the end of the game when both players take optimal steps?

Constraints

  • 1\leq N\leq 2\times 10^5
  • 1\leq A_i, B_i\leq 10^9 (1\leq i \leq N)
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N

Output

Print the answer as an integer.

Sample Input 1

3
6 4
2 1
5 3

Sample Output 1

12

In the initial state, the numbers written on the face-up sides are 6,2,5. One possible progression from here is as follows.

  1. Alice flips the first card. Then, the numbers written on the face-up sides are 4,2,5. Bob removes the third card and scores 5 points.
  2. Alice flips the second card. Then, the numbers written on the face-up sides are 4,1. Bob removes the second card and scores 1 point.
  3. Alice flips the first card, the final one remaining. Then, the number written on the face-up side is 6. Bob removes it and scores 6 points.

In this case, Bob's final score is 12 points. In fact, this progression is an example of optimal sequences of moves for both players; the answer is 12.

Sample Input 2

5
166971716 552987438
219878198 619875818
918378176 518975015
610749017 285601372
701849287 307601390

Sample Output 2

3078692091