Taco Task Scheduling

You are given a set of tasks with non-negative execution times. Your objective is to schedule these tasks on two processors working in parallel such that the maximum load between the two processors is minimized.

Formally, let there be N tasks with execution times t₁, t₂, ..., t_N and let the total execution time be S = t₁ + t₂ + ... + t_N. You want to partition the tasks into two subsets, say S1 and S2, such that you minimize the quantity \[ \max\left(\sum_{t \in S1} t, \sum_{t \in S2} t\right), \] which represents the minimal maximum execution time for two processors.

You will be given multiple test cases. For each test case, determine the minimal possible maximum load that can be achieved by an optimal partitioning of the tasks across the two processors.

inputFormat

The input is given via standard input (stdin) and has the following format:

T
N1
t1 t2 ... tN1
N2
t1 t2 ... tN2
... (for T test cases)

Where:

• T is the number of test cases.
• For each test case, the first line contains N, the number of tasks.
• The next line contains N space-separated non-negative integers, each representing the execution time of a task.

outputFormat

For each test case, output a single line via standard output (stdout) with one integer: the minimum possible maximum execution time achievable by an optimal partition of the tasks.

## sample

2
5
1 2 3 4 5
4
10 10 10 10

8
20

</p>