配点 : $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}$

出力

答えを出力せよ。

3
1 2 3 4 5 6

15

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

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

4
1 4 5 8 7 6 3 2

20