【题目描述】

有 $T$ 组数据。商店有两个结账窗口和 $n$ 名顾客，第 $i$ 名顾客结账需要 $a_i$ 时间。

每名顾客必须选择一个窗口，同一窗口依次结账。请合理分配，使两个窗口中较晚结束的时间尽量小，输出这个最小时间。

【输入格式】

$T$

$n$

$a_1$   $\cdots$   $a_n$

$\vdots$

【输出格式】

每组输出一行最早关门时间。

【样例】

2
3
2 3 5
4
1 1 1 1

5
2

【数据范围】

• $1\le T\le100$
• $1\le n\le15$
• $1\le a_i\le10^9$