Minimum Completion Time with Two Processors

You are given a set of tasks and two processors. Each task has a specified duration. Your objective is to assign each task to one of the two processors such that the overall completion time is minimized. The overall completion time is defined as the maximum sum of task durations assigned to either processor.

More formally, if the tasks are divided into two groups A and B with durations \(a_1, a_2, \ldots, a_k\) and \(b_1, b_2, \ldots, b_m\) respectively, then the completion time is given by:

[ T_{min} = \max\left(\sum_{i=1}^{k} a_i, \sum_{j=1}^{m} b_j\right)]

You are required to perform the assignment using a greedy strategy: sort the task durations in descending order and assign each task to the processor that currently has the lower total load. This approach yields the minimum possible completion time for the given set of tasks.

inputFormat

The first line contains an integer T representing the number of test cases. For each test case:

• The first line contains an integer N, the number of tasks.
• The second line contains N space-separated integers representing the durations of the tasks.

outputFormat

For each test case, output a single line containing the minimum total completion time achievable by assigning the tasks optimally to two processors.

## sample

1
1
5

5

</p>