Migrated from Lutece 3199 折叠 n 截棍

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

qzr 有一把 n 截棍，具体来说， n 截棍有 n 根木棍首尾相接组成，第 i 根木棍长度为 $a_i$ ,由于未知原因， 木棍的直径可以忽略不计，即可以看作线段。现在qzr 希望制作一个竹筒用来装 n 截棍，但是竹子的长度有限，所以 qzr 希望你告诉他最少多长的竹筒可以装下 n 截棍。例如 n 截棍有长度为 3，2，2，3 的四截木棍组成，qzr可以制作一个长度为 3 的竹筒，将 n 截棍程 M 型折叠起来放进竹筒。

Input

第一行一个正整数 T ，代表数据组数。 每组数据第一行一个正整数 n ，代表木棍根数。 第二行 n 个正整数 $a_1,a_2,...,a_n$ ，代表每根木棍的长度。

Output

每组数据输出一行，代表最短的竹筒长度。

Samples

6
2
1 3
3
1 2 3
4
6 2 3 9
4
6 8 4 5
7
1 2 4 6 7 7 3
8
8 6 5 1 2 2 3 6

3
3
9
9
7
8

Constraints

1<=t<=1000 1<=n<=10000 1<=$a_i$<=1000 保证所有 n 的总和不超过 10000。

Note

对于第三组数据，我们可以按如下方式折叠 假设第一根木棍的左端点的坐标为 0，于是右端点的坐标为 6。我们用 [0,6] 代表第一根木棍的位置。那么四根木棍的位置依次为 [0,6]→[4,6]→[4,7]→[−2,7] ，我们可以用 [-2,7] 这样长度为 9 的竹筒将 n 截棍装下。

对于第四组数据，木棍的位置为 [0,6]→[−2,6]→[−2,2]→[2,7]，我们可以用 [-2.7] 这样长度为9 的竹筒将 n 截棍装下。

Resources

2024 UESTC ICPC Training for Search and Dynamic Programming