CF2252A Boss Fight

你正在与一个拥有未知生命值的 Boss 战斗。你有一组 $n$ 张法术卡，第 $i$ 张卡造成 $a_i$ 点伤害。你可以任意重排列你的手牌，并按任意顺序出牌。 Boss 有一个自适应护盾。如果你连续打出两张伤害值完全相同的卡牌，护盾会永久激活。触发护盾的那张牌依然会造成正常伤害，但你随后打出的所有卡将只造成 $0$ 伤害。 请问，如果你最佳地安排出牌顺序，Boss 的最大生命值是多少，他才会刚好被你打败？

每个测试点包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \leq t \leq 100$）。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 50$），表示法术卡的数量。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 1000$），分别表示每张卡造成的伤害。

对于每个测试用例，输出一个整数，代表 Boss 最大可以拥有的生命值，使得你一定能击败他。

在第一个测试用例中，你只有 $1$ 张卡。你打出它，造成 $100$ 点伤害。 在第二个测试用例中，你可以将手牌排列为 $[10, 5, 10, 10]$。你先打出一个 10，再打出 5，然后是第二个 10，最后是第三个 10。因为你连续打出了两个 10，护盾会激活。但触发护盾的那张牌仍然会造成正常伤害。总伤害为 $10 + 5 + 10 + 10 = 35$。 在第三个测试用例中，所有卡牌值都不同。你可以随意出牌，总伤害即是所有卡的和：$1 + 2 + 3 + 4 + 5 = 15$。 在第四个测试用例中，所有 $6$ 张牌伤害都是 7。无论你如何出牌，第二张卡都会和第一张重复。第二张牌会触发护盾并造成正常伤害，后面所有卡只能造成 $0$ 伤害。总伤害是 $7+7=14$。 由 ChatGPT 5 翻译