← 返回题目列表

Codeforces · 1930/A

A. 最大化分数

中文机器翻译题面 查看原题

白板上写着 $$$2n$$$ 个正整数。由于无聊,您决定用白板上的数字玩一个单人游戏。

您的起始分数为 $$$0$$$。通过精确执行以下动作 $$$n$$$ 次,您将提高分数:

- 选择写在白板上的两个整数 $$$x$$$ 和 $$$y$$$。
- 将 $$$\min(x,y)$$$ 添加到您的分数中。
- 从白板上擦除 $$$x$$$ 和 $$$y$$$。

请注意,执行移动 $$$n$$$ 次后,白板上将不再写入任何整数。

找出如果您以最佳方式执行 $$$n$$$ 动作,您可以获得的最高最终分数。

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 5000$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 50$$$) - 白板上写的整数数量是 $$$2n$$$。

每个测试用例的第二行包含 $$$2n$$$ 整数 $$$a_1,a_2,\ldots,a_{2n}$$$ ($$$1 \leq a_i \leq 10^7$$$) - 白板上写的数字。

输出

对于每个测试用例,输出您可以获得的最高最终分数。

示例

输入 #1

3
1
2 3
2
1 1 2 1
3
1 1 1 1 1 1

输出 #1

2
2
3

注意

在第一个测试用例中,您只能移动一步。您选择$$$x=2$$$ 和$$$y=3$$$,您的分数将为$$$\min(x,y)=2$$$。

在第二个测试用例中,以下是最终得分为 $$$2$$$ 的一系列移动:

- 在第一步中,选择 $$$x=1$$$ 和 $$$y=1$$$。然后,将 $$$\min(x,y)=1$$$ 添加到分数中。擦掉$$$x$$$和$$$y$$$后,白板上剩下的整数是$$$1$$$和$$$2$$$。
- 在第二步中,选择 $$$x=1$$$ 和 $$$y=2$$$。然后,将 $$$\min(x,y)=1$$$ 添加到分数中。删除 $$$x$$$ 和 $$$y$$$ 后,白板上将不再留下任何整数。

在第三个测试用例中,您将执行三次移动,每次将 $$$1$$$ 添加到分数中。