G. Минимальное покрытие
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Даны $$$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$$$ строк, каждая из которых содержит ответ на соответствующий набор входных данных. В качестве ответа выведите одно целое число — минимальную достижимую длину покрытия оси заданными отрезками.

Пример
Входные данные
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
Примечание

В третьем наборе входных данных из примера отрезки следует расположить следующим образом: $$$[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$$$.