给定了 $$$n$$$ 段的长度,这些段需要放置在带有坐标的无限轴上。
将第一段放置在轴上,使其端点之一位于坐标 $$$0$$$ 的点处。我们将此端点称为第一个段的“开始”,并将其“结束”称为不是开始的端点。
随后每个段的“开始”必须与前一个段的“结束”一致。因此,如果下一个线段的长度为 $$$d$$$ 并且前一个线段的“结束”坐标为 $$$x$$$,则该线段可以放置在坐标 $$$[x-d, x]$$$ 上,然后其“结束”坐标为 $$$x - d$$$,或者放置在坐标 $$$[x, x+d]$$$ 上,在这种情况下其“结束”坐标为 $$$x + d$$$。
这些线段对轴的总覆盖范围定义为它们的整体并集,它基本上是至少一个线段覆盖的点集。很容易证明覆盖范围也将是轴上的一段。确定通过将所有线段放置在轴上而不改变其顺序可以获得的最小可能覆盖长度。
输入
第一行包含一个整数 $$$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$$$。
输出
打印 $$$t$$$ 行,每行包含相应测试用例的答案。测试用例的答案应该是一个整数——轴覆盖范围的最小可能长度。
示例
输入 #1
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
输出 #1
3 3 9 9 7 8
注意
在第三个示例测试用例中,段应按如下方式排列:$$$[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$$$。