You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

制作猪饲料

时间限制：$1s$

空间限制：$256MB$

题目背景：

今天，$piggy$要制作猪饲料

题目描述：

$piggy$有两个制作猪饲料的机器，今天送来了$n$堆草垛，机器处理每个草垛的时间是$t_i$，两个机器可以同时运行，求最小花费时间，使得所有草垛都被制作成猪饲料

输入描述：

第一行一个整数T，表示共T组数据
接下来T组数据：
第一行一个整数n
第二行包含n个整数，表示t_i

输出描述：

共T行，每行一个整数，表示最小花费时间

样例输入：

2
2
1 1
5
1 2 3 4 5

样例输出：

1
8

数据范围：

$40pts$： $n \leq 20$

$100pts$：$n \leq 1000 \sum t_i \leq 100000$

保证$t_i$为正整数,$\sum n \leq 1000$