CF2252A.Boss Fight

You are fighting a boss with an unknown amount of health. You have a sequence of $n$ spell cards, where the $i$-th card deals $a_i$ damage. You can rearrange your hand and play the cards in any order you choose.

The boss has an adaptive shield. If you ever play two cards in a row that deal the exact same amount of damage, the shield permanently activates. The card that triggers the shield still deals its normal damage, but all subsequent cards you play will deal $0$ damage.

Find the maximum total health the boss can have such that you will defeat him if you arrange and play your cards optimally.

你正在挑战一个血量未知的 Boss。你手中有 $n$ 张法术卡牌组成的序列，其中第 $i$ 张卡牌造成 $a_i$ 点伤害。你可以重新排列手牌，并以任意顺序打出这些卡牌。

Boss 拥有一个自适应护盾：若你连续打出两张造成完全相同伤害的卡牌，则该护盾将永久激活。触发护盾的那张卡牌仍造成其正常伤害，但此后你打出的所有卡牌均造成 $0$ 点伤害。

求 Boss 的最大可能血量，使得只要你以最优方式排列并打出卡牌，就一定能击败他。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 50$) — the number of spell cards.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 1000$) — the damage dealt by each card.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 100$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 50$）—— 表示法术卡牌的数量。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 1000$）—— 表示每张卡牌造成的伤害。

For each test case, output a single integer — the maximum total health the boss can have such that you will defeat him.

对于每个测试用例，输出一个整数——即老板可能拥有的最大总生命值，使得你能够击败他。

In the first test case, you have only $1$ card. You play it, dealing $100$ damage.

In the second test case, you can arrange your hand as $[10, 5, 10, 10]$. You play the first 10. Then you play the 5. Then you play the second 10. Then you play the final 10. Because you played two 10s in a row, the shield activates. However, the card that triggers the shield still deals its normal damage. The total damage dealt is $10 + 5 + 10 + 10 = 35$.

In the third test case, all cards are distinct. You can simply play them in any order to deal the sum of their damage: $1 + 2 + 3 + 4 + 5 = 15$.

In the fourth test case, all $6$ cards deal exactly 7 damage. No matter what order you play them in, your second card will be identical to your first. The second card will trigger the shield and deal its normal damage, but the remaining $4$ cards will deal $0$ damage. The total damage dealt is $7 + 7 = 14$.

在第一个测试用例中，你只有一张牌。你打出这张牌，造成 $100$ 点伤害。

在第二个测试用例中，你可以将手牌排列为 $[10, 5, 10, 10]$。你先打出第一张 $10$，再打出 $5$，接着打出第二张 $10$，最后打出最后一张 $10$。由于你连续打出两张 $10$，护盾被触发。然而，触发护盾的那张牌仍造成其正常伤害。总伤害为 $10 + 5 + 10 + 10 = 35$。

在第三个测试用例中，所有牌的数值均不相同。你可以以任意顺序打出它们，造成其伤害值之和：$1 + 2 + 3 + 4 + 5 = 15$。

在第四个测试用例中，全部 $6$ 张牌均造成恰好 $7$ 点伤害。无论你以何种顺序打出这些牌，你的第二张牌必然与第一张牌相同。第二张牌将触发护盾并造成其正常伤害，但剩余的 $4$ 张牌将造成 $0$ 点伤害。总伤害为 $7 + 7 = 14$。