← 返回题目列表

Codeforces · 2130/A

A. 提交就是你所需要的

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

对于由非负整数组成的多重集 $$$T$$$,我们定义:

  • $$$\text{sum}(T)$$$ 是 $$$T$$$ 中所有元素的总和。例如,如果 $$$T = \{0,1, 1, 3\}$$$,则 $$$\text{sum}(T)= 0+1+1+3=5$$$。

  • $$$\text{mex}(T)$$$ 是不在 $$$T$$$ 中的最小非负整数。例如,如果 $$$T = \{0,1, 1, 3\}$$$,则 $$$\text{mex}(T) = 2$$$,因为 $$$2$$$ 是 $$$T$$$ 中不存在的最小非负整数。
给你一个多重集$$$S$$$,大小为$$$n$$$,由非负整数组成。首先,您的分数是 $$$0$$$。您可以按任意顺序执行以下操作任意次数(可能为零):
  • 选择子集 $$$S' \subseteq S$$$(即 $$$S'$$$ 包含 $$$S$$$ 中当前的一些元素),将 $$$\text{sum}(S')$$$ 添加到您的分数,然后从 $$$S$$$ 中删除 $$$S'$$$。
  • 选择子集 $$$S' \subseteq S$$$,将 $$$\text{mex}(S')$$$ 添加到您的分数中,然后从 $$$S$$$ 中删除 $$$S'$$$。

找出可以获得的最大可能分数。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^3$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 50$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$S_1, S_2, \ldots, S_n$$$ ($$$0 \le S_i \le 50$$$)。

输出

对于每个测试用例,打印一个整数 - 可以获得的最大可能分数。

示例

输入
复制

2
3
0 1 1
3
1 2 3

输出
复制

3
6

注意

在第一个测试用例中,可能的最优策略如下:

  • 选择 $$$S'=\{0,1\}$$$,将 $$$\text{mex}(S')=\text{mex}(\{0,1\})=2$$$ 添加到您的乐谱中,然后从 $$$S$$$ 中删除 $$$S'$$$。目前,您的分数为 $$$2$$$ 且 $$$S=\{1\}$$$。
  • 选择 $$$S'=\{1\}$$$,将 $$$\text{sum}(S')=\text{sum}(\{1\})=1$$$ 添加到您的分数中,然后从 $$$S$$$ 中删除 $$$S'$$$。目前,您的分数为 $$$3$$$ 且 $$$S=\varnothing$$$。

之后,您将无法进行任何进一步的操作。可以证明$$$3$$$是可以获得的最大可能分数。