Maximize Subset Sum with Balanced Partition

In this problem, you are given an array of integers for each test case. Your task is to partition the array into two subsets: subset A and subset B such that the number of elements in subset A is greater than or equal to the number of elements in subset B, and the sum of elements in subset A is maximized.

Formally, let ( n ) be the number of elements in the array. You are to choose ( k ) elements (where ( k \geq \lceil n/2 \rceil )) and maximize the sum of these chosen elements. It can be shown that choosing the ( \lceil n/2 \rceil ) largest elements yields the optimal solution. Your solution should read from standard input and print the result for each test case on a new line.

inputFormat

The input begins with an integer ( t ) representing the number of test cases. For each test case, the first line contains an integer ( n ) (the size of the array), followed by a line containing ( n ) space-separated integers.

outputFormat

For each test case, output a single line containing an integer, which is the maximum possible sum of subset A.## sample

3
4
1 2 3 4
5
1 1 1 1 1
6
3 3 3 3 3 3

7
3
9