题目描述

有 $2N$ 张卡片，每张卡片上标有 $1$ 到 $2N$ 的编号。卡片 $i$ 的价值为 $V_i$。高桥君和青木君按照以下步骤重复 $N$ 次，将卡片分配为各自 $N$ 张：

• 首先，高桥君从尚未被选中的卡片中选择一张，归自己所有。然后，青木君从尚未被选中的卡片中选择编号为中位数的那一张，归自己所有。

请你求出高桥君最终能获得的卡片价值总和的最大值。

输入格式

输入以如下格式从标准输入读入：

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

输出格式

请输出答案。

样例 1

输入

3
1 2 3 4 5 6

输出

15

样例 2

输入

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$ 是整数

样例解释 1

按照如下步骤，高桥君可以获得卡片 $4,5,6$：

• 首先，高桥君选择卡片 $6$，然后青木君选择卡片 $3$。
• 接着，高桥君选择卡片 $5$，然后青木君选择卡片 $2$。
• 最后，高桥君选择卡片 $4$，然后青木君选择卡片 $1$。

由 ChatGPT 4.1 翻译