... и шитья
Задачу добавил: alef
Успешно сдано решений: 31
Время на тест - 1 с
Когда скатерть была разрезана на салфетки, в залу вновь вошли двое в темно-синих плащах, что-то вновь сказали человечку, затем уложили салфетки в стопки и унесли их.
Человечек подошел к друзьям и объявил им:
- Великий маг доволен, что вы справились с заданием. Но он просит вас сделать еще кое-что...
Следующее задание Ормуса состояло в том, чтобы сшить оставшиеся разноцветные квадраты в тесьму - шириной в один квадрат и максимально возможной длины. Однако квадраты одного цвета не должны соприкасаться друг с другом сторонами. Кроме того, тесьма должна начинаться и заканчиваться квадратами разного цвета.
Ваша задача - по заданному набору квадратов определить максимально возможную длину тесьмы.
Формат входного файла input.txt
Первая строка - целое число K (1 <= K <= 10) - количество наборов квадратов
Затем следует K блоков описаний квадратов
Первая строка блока - целое число C (1 <= C <= 20) - количество различных цветов
Вторая строка блока содержит C целых чисел S1, S2, ..., SC через пробел. Число Sj (j = 1, 2, ..., C) - количество квадратов цвета j
Формат выходного файла output.txt
В каждой из K строк содержится по одному числу - максимальной длине тесьмы, которая может получиться из квадратов согласно условию задачи.
Пример входного файла
1
2
20 1
Пример выходного файла
2