CF1579G Minimal Coverage

**本题有多组测试数据。** 给你 $n$ 条线段，告诉你每条线段的长度。 你需要把它们**依次**放在一条无限长的数轴上。 放置需满足当前线段的起点是前一个线段的终点。特别地，第一个线段的起点为 $0$。 也就是说，若前一个线段的终点是 $x$,当前长度为 $d$, 那么这个线段必须放在 $[x−d,x]$ 终点变为 $x−d$，或 $[x,x+d]$ 终点变为 $x+d$。 请问放置完后所有线段的最小覆盖长度是多少？

第一行一个整数 $t$，表示数据组数。 对于每组数据： 第一行一个整数 $n$，表示线段总数。 第二行 $n$ 个整数，表示 $n$ 条线段的长度。

$t$ 行，每行一个整数，第 $i$ 行表示第 $i$ 组数据的答案。

$1\le t\le 1000$，$1\le\sum n\le10^4$，$1\le a_i\le 1000$。