题目描述

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

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

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

输入格式

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

$N$ $V_1$ $V_2$ $\cdots$ $V_{2N}$

输出格式

答えを出力せよ。

题目大意

有 $2N$ 张牌，编号为 $1\sim 2N$，第 $i$ 张牌价值 $V_i$。现在 Takahashi 和 Aoki 轮流取牌，每次 Takahashi 先取一张没有被取过的牌，之后 Aoki 取编号为剩余牌编号中位数的牌。重复以上步骤 $N$ 次，两人各取 $N$ 张牌。

请求出 Takahashi 取到的牌价值之和的最大值。

输入第一行一个整数 $N$，第二行 $N$ 个整数 $V_1,V_2,\cdots,V_N$。

• $1\leqslant N\leqslant 2\times 10^5$；

• $0\leqslant V_i\leqslant 10^9$；

• $V_i$ 均为整数。

3
1 2 3 4 5 6

15

4
1 4 5 8 7 6 3 2

20

提示

制約

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

Sample Explanation 1

以下のような手順で、高橋君はカード $4,5,6$ を手にすることができます。 - まず、高橋君はカード $6$ を選ぶ。そして、青木君はカード $3$ を選ぶ。 - 次に、高橋君はカード $5$ を選ぶ。そして、青木君はカード $2$ を選ぶ。 - 最後に、高橋君はカード $4$ を選ぶ。そして、青木君はカード $1$ を選ぶ。