B - Taking the middle Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 700 点

問題文

2N 枚のカードがあり、それぞれには 1 から 2N までの番号が付いています。カード i の価値は V_i です。 高橋君と青木君は以下の手順を N 回繰り返し、カードを N 枚ずつに分配します。

  • まず、高橋君がまだ選ばれてないカードの中から 1 枚選び、自分のものとする。 その後、青木君はまだ選ばれてないカードのうち 番号 が中央値であるものを選び、自分のものとする。

高橋君が最終的に持っているカードの価値の総和として考えられる最大の値を求めてください。

制約

  • 1\leq N\leq 2\times 10^5
  • 0\leq V_i\leq 10^9
  • V_i は整数

入力

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

N
V_1 V_2 \cdots V_{2N}

出力

答えを出力せよ。

入力例 1

3
1 2 3 4 5 6

出力例 1

15

以下のような手順で、高橋君はカード 4,5,6 を手にすることができます。

  • まず、高橋君はカード 6 を選ぶ。そして、青木君はカード 3 を選ぶ。
  • 次に、高橋君はカード 5 を選ぶ。そして、青木君はカード 2 を選ぶ。
  • 最後に、高橋君はカード 4 を選ぶ。そして、青木君はカード 1 を選ぶ。

入力例 2

4
1 4 5 8 7 6 3 2

出力例 2

20

Score : 700 points

Problem Statement

We have 2N cards, with ID numbers from 1 through 2N. Card i has a value of V_i. Takahashi and Aoki will do the following procedure N times so that each of them gets N cards.

  • First, Takahashi chooses one card that is not yet chosen and gets it. Then, Aoki chooses the card whose ID number is the median of those of the cards not yet chosen and gets it.

Find the maximum possible sum of the values of cards Takahashi has in the end.

Constraints

  • 1\leq N\leq 2\times 10^5
  • 0\leq V_i\leq 10^9
  • V_i is an integer.

Input

Input is given from Standard Input in the following format:

N
V_1 V_2 \cdots V_{2N}

Output

Print the answer.

Sample Input 1

3
1 2 3 4 5 6

Sample Output 1

15

Takahashi can get Cards 4, 5, and 6 as follows:

  • First, Takahashi chooses Card 6, which makes Aoki choose Card 3.
  • Next, Takahashi chooses Card 5, which makes Aoki choose Card 2.
  • Lastly, Takahashi chooses Card 4, which makes Aoki choose Card 1.

Sample Input 2

4
1 4 5 8 7 6 3 2

Sample Output 2

20