CF1579G.Minimal Coverage

You are given $n$ lengths of segments that need to be placed on an infinite axis with coordinates.

The first segment is placed on the axis so that one of its endpoints lies at the point with coordinate $0$. Let's call this endpoint the "start" of the first segment and let's call its "end" as that endpoint that is not the start.

The "start" of each following segment must coincide with the "end" of the previous one. Thus, if the length of the next segment is $d$ and the "end" of the previous one has the coordinate $x$, the segment can be placed either on the coordinates $[x-d, x]$, and then the coordinate of its "end" is $x - d$, or on the coordinates $[x, x+d]$, in which case its "end" coordinate is $x + d$.

The total coverage of the axis by these segments is defined as their overall union which is basically the set of points covered by at least one of the segments. It's easy to show that the coverage will also be a segment on the axis. Determine the minimal possible length of the coverage that can be obtained by placing all the segments on the axis without changing their order.

给你 $n$ 条线段的长度，需将它们放置在一条无限长的数轴上。

第一条线段被放置在数轴上，使其一个端点恰好位于坐标为 $0$ 的点。我们称该端点为第一条线段的“起点”，而另一个端点（即非起点的端点）则称为其“终点”。

此后每条线段的“起点”必须与前一条线段的“终点”重合。因此，若下一条线段的长度为 $d$，且前一条线段的“终点”位于坐标 $x$，则该线段可被放置在区间 $[x-d, x]$ 上（此时其“终点”坐标为 $x - d$），也可被放置在区间 $[x, x+d]$ 上（此时其“终点”坐标为 $x + d$）。

这些线段在数轴上的总覆盖长度定义为它们的并集（即至少被其中一条线段覆盖的所有点构成的集合）。容易证明，该并集本身也构成数轴上的一段连续区间。请确定：在不改变线段顺序的前提下，通过合理选择每条线段的放置方向（向左或向右延伸），所能达到的最小可能覆盖长度。

The first line contains an integer $t$ ($1 \leq t \leq 1000$) — the number of test cases.

The next $2t$ lines contain descriptions of the test cases.

The first line of each test case description contains an integer $n$ ($1 \le n \le 10^4$) — the number of segments. The second line of the description contains $n$ space-separated integers $a_i$ ($1 \le a_i \le 1000$) — lengths of the segments in the same order they should be placed on the axis.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^4$.

第一行包含一个整数 $t$（$1 \leq t \leq 1000$）—— 测试用例的数量。

接下来的 $2t$ 行包含各测试用例的描述。

每个测试用例描述的第一行包含一个整数 $n$（$1 \le n \le 10^4$）—— 线段的数量。描述的第二行包含 $n$ 个以空格分隔的整数 $a_i$（$1 \le a_i \le 1000$）—— 各线段的长度，按其在坐标轴上放置的顺序给出。

保证所有测试用例中 $n$ 的总和不超过 $10^4$。

Print $t$ lines, each line containing the answer to the corresponding test case. The answer to a test case should be a single integer — the minimal possible length of the axis coverage.

输出 $t$ 行，每行包含对应测试用例的答案。每个测试用例的答案应为一个整数——即坐标轴覆盖的最小可能长度。

In the third sample test case the segments should be arranged as follows: $[0, 6] \rightarrow [4, 6] \rightarrow [4, 7] \rightarrow [-2, 7]$. As you can see, the last segment $[-2, 7]$ covers all the previous ones, and the total length of coverage is $9$.

In the fourth sample test case the segments should be arranged as $[0, 6] \rightarrow [-2, 6] \rightarrow [-2, 2] \rightarrow [2, 7]$. The union of these segments also occupies the area $[-2, 7]$ and has the length of $9$.

在第三个样例测试用例中，线段应按如下顺序排列：$[0, 6] \rightarrow [4, 6] \rightarrow [4, 7] \rightarrow [-2, 7]$。如你所见，最后一个线段 $[-2, 7]$ 覆盖了所有先前的线段，总覆盖长度为 $9$。

在第四个样例测试用例中，线段应按 $[0, 6] \rightarrow [-2, 6] \rightarrow [-2, 2] \rightarrow [2, 7]$ 的顺序排列。这些线段的并集同样占据区间 $[-2, 7]$，其长度为 $9$。