Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
 User ID: Password:
Register

Language:
Regions
 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 234 Accepted: 124

Description

The new election system was introduced in our republic. The system is based on a majority of votes in regions. The republic is divided into M regions, each of them means exactly one seat in the Parliament.

The Chairman of PSOS would like to know how many voters makes the certainty that PSOS win the election. To win the election means to get more than one half of Parliament seats. We do not know the exact number of political Parties participating in election but we can determine the number of voters in every region. We can assume that all voters will participate in election and each of them will give his/her vote to one of the candidates. PSOS have their candidates in all regions. At least one another party has its candidate in each of the regions. You are to determine the minimum number of votes which ensures the landslide of PSOS, even in the worst possible case.

Input

At the first line there is a positive integer N stating the number of assignments to follow. Each assignment consists of two lines. The first line contains an integer number M stating the number of regions. At the second line, there are exactly M numbers separated by spaces. These numbers state the number of voters in each of the regions. All the number are possitive and less or equal to 100000.

Output

Print a single line for each assignment. The line must contain the sentence "H hlasu zajisti strane vitezstvi." (H votes ensures the win of Party). Instead of H, fill the minimum number of votes which ensures the win.

Sample Input

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

Sample Output

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

Source

[Submit]   [Go Back]   [Status]   [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator