Даны \(n\) длин отрезков, которые требуется уложить на бесконечной координатной оси.
Первый отрезок откладывается на оси так, чтобы один из его концов лежал в точке с координатой \(0\). Назовем этот конец «началом» первого отрезка, а его «концом» — тот его конец, который не является началом.
«Начало» каждого следующего отрезка должно совпадать с «концом» предыдущего. Таким образом, если длина очередного отрезка равна \(d\), а «конец» предыдущего имеет координату \(x\), отрезок может быть расположен либо на координатах \([x-d, x]\), и тогда координата его «конца» равна \(x - d\), либо на координатах \([x, x+d]\), и в этом случае координата его «конца» равна \(x + d\).
Суммарное покрытие оси отрезками определяется как объединение всех отрезков, то есть как множество точек, покрытых хотя бы одним из них. Несложно показать, что покрытие тоже будет отрезком на оси. Определите минимальную возможную длину покрытия, которую можно получить, проложив все отрезки на оси, не меняя их порядка.
Выходные данные
Выведите \(t\) строк, каждая из которых содержит ответ на соответствующий набор входных данных. В качестве ответа выведите одно целое число — минимальную достижимую длину покрытия оси заданными отрезками.
Примечание
В третьем наборе входных данных из примера отрезки следует расположить следующим образом: \([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\).
Примеры
| № | Входные данные | Выходные данные |
|
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
|
3
3
9
9
7
8
|