Minimum Makespan Scheduling on Two Machines

You are given a set of tasks with positive integer processing times. Your goal is to assign each task to one of two machines such that the overall completion time (the makespan) is minimized. The two machines work in parallel, and the makespan is determined by the machine that finishes last.

Let \(S\) be the total processing time of all tasks. We want to partition the tasks into two subsets such that if the sum of processing times in one subset is \(x\), then the other subset has a sum of \(S-x\), and the objective is to minimize \(\max(x, S-x)\). This typical partition problem can be solved using dynamic programming.

inputFormat

The input is read from standard input (stdin) and has the following format:

T
n1
val1,1 val1,2 ... val1,n1
n2
val2,1 val2,2 ... val2,n2
...

Here, the first line contains an integer \(T\) representing the number of test cases. For each test case, the first integer is \(n\) - the number of tasks, followed by \(n\) space-separated integers denoting the processing times of the tasks.

outputFormat

For each test case, output a single integer in a separate line, the minimum possible makespan when scheduling the tasks on two machines.

## sample

2
4
3 1 4 2
3
2 3 5

5
5

</p>