题目描述

我国新引入了一种基于地区多数票的选举制度。全国划分为 $M$ 个地区，每个地区对应议会中的一个席位。PSOS（某政党）的主席想知道需要多少选民才能确保该党赢得选举。赢得选举意味着获得超过一半的议会席位。我们不知道具体有多少政党参与选举，但可以确定每个地区的选民数量。假设所有选民都会参与投票，并且每位选民会将票投给其中一个候选人。PSOS在所有地区都有自己的候选人，并且每个地区至少有一个其他政党也有候选人。你需要确定在最坏情况下，确保PSOS获胜所需的最小票数。

输入格式

• 第一行是一个正整数 $N$，表示测试用例的数量。
• 每个测试用例包含两行：
  • 第一行是一个整数 $M$，表示地区的数量。
  • 第二行是 $M$ 个正整数，表示每个地区的选民数量，所有数字不超过100000。

输出格式

对于每个测试用例，输出一行："H hlasu zajisti strane vitezstvi."（H 票确保政党获胜），其中 $H$ 是确保获胜所需的最小票数。

示例输入 1

3
10
340 260 180 15 1 20 40 90 78 34
2
12 1
6
1 2 3 4 5 6

示例输出 1

1003 hlasu zajisti strane vitezstvi.
13 hlasu zajisti strane vitezstvi.
18 hlasu zajisti strane vitezstvi.

来源

CTU FEE Local 1998