26A. Opening the Bags

500 pts2s256 MB

Alice and Bob have $n$ bags of candies, described by an array $a_1, a_2, \ldots, a_n$ : bag $i$ contains $a_i$ candies.

Alice first arranges all the bags in any order. They then open the bags in that order, taking turns, starting with Alice.

Whenever a bag is opened, its candies are divided as evenly as possible between Alice and Bob. If there is one extra candy, the person who opened that bag receives it.

All bags must be opened. Candies from different bags cannot be combined before they are divided.

For each test case, find the maximum total number of candies Alice can receive.

Constraints

$1 \leq t \leq 10^3$
$1 \leq n \leq 100$
$1 \leq a_i \leq 10^6$
The sum of $n$ over all test cases is at most $10^5$ .

Input

t

\left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \ldots \quad a_n \end{array} \right\} \times t

Output

\left. \begin{array}{l} \mathrm{answer} \end{array} \right\} \times t

Samples

Input

Case 1

4
2 9 4 7

Case 2

4
1 3 5 7

Explanation

Case 1

Alice can arrange the bags as $9,2,7,4$ . She opens the first and third bags and receives $5+1+4+2=12$ candies in total. This is the maximum possible.

Case 2

With the bags in the given order, Alice receives $1+1+3+3=8$ candies. Every ordering gives her the same total in this case.

Output

Case 1

Case 2

Input

Case 1

1
5

Case 2

3
4 6 8

Case 3

5
2 3 8 1 4

Explanation

Case 1

Alice opens the only bag. She receives $3$ candies, and Bob receives $2$ .

Case 2

Every bag can be split equally. Alice receives $2+3+4=9$ candies, regardless of the order.

Case 3

Alice can arrange the bags as $3,2,1,8,4$ . She receives $2+1+1+4+2=10$ candies in total, which is the maximum possible.

Output

Case 1

Case 2

Case 3

Alice and Bob have $n$ bags of candies, described by an array $a_1, a_2, \ldots, a_n$ : bag $i$ contains $a_i$ candies.

Alice first arranges all the bags in any order. They then open the bags in that order, taking turns, starting with Alice.

Whenever a bag is opened, its candies are divided as evenly as possible between Alice and Bob. If there is one extra candy, the person who opened that bag receives it.

All bags must be opened. Candies from different bags cannot be combined before they are divided.

For each test case, find the maximum total number of candies Alice can receive.

$1 \leq t \leq 10^3$
$1 \leq n \leq 100$
$1 \leq a_i \leq 10^6$
The sum of $n$ over all test cases is at most $10^5$ .

t

\left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \ldots \quad a_n \end{array} \right\} \times t

\left. \begin{array}{l} \mathrm{answer} \end{array} \right\} \times t

Alice can arrange the bags as $9,2,7,4$ . She opens the first and third bags and receives $5+1+4+2=12$ candies in total. This is the maximum possible.

With the bags in the given order, Alice receives $1+1+3+3=8$ candies. Every ordering gives her the same total in this case.

Alice opens the only bag. She receives $3$ candies, and Bob receives $2$ .

Every bag can be split equally. Alice receives $2+3+4=9$ candies, regardless of the order.

Alice can arrange the bags as $3,2,1,8,4$ . She receives $2+1+1+4+2=10$ candies in total, which is the maximum possible.

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

26A. Opening the Bags

Constraints

Input

Output

Samples

26A. Opening the Bags

Constraints

Input

Output

Samples