Линия монорельса, построенная в столице Байтландии, не пользуется особой популярностью среди пассажиров. Изучив ситуацию, специалисты по транспортным потокам пришли к выводу, что место для постройки было выбрано очень неудачно. Равно как и конфигурация линии. Дело в том, что для популярности у жителей столицы новая линия должна быть кольцевой. А ещё лучше — если это были бы две кольцевые линии в разных районах города. В итоге было решено разобрать монорельсовую дорогу и из прямолинейных участков построить две примерно одинаковые кольцевые линии. Каждая линия представляет собой многоугольник, собранный из прямолинейных участков существующей линии. При этом многоугольник должен иметь ненулевую площадь, каждый участок существующей линии должен быть использован в новых сооружениях ровно один раз, участки должны быть использованы целиком «как есть» (то есть разрезание прямолинейного участка не допускается).

Мэрия хочет, чтобы длины каждой кольцевой линии (то есть периметры многугольников) отличались как можно меньше. Ваша задача — найти эту минимальную разницу или определить, что строительство двух кольцевых линий из существующего набора прямолинейных участков невозможно.

Формат ввода
Первая строка входных данных содержит одно целое число N (6 ≤ N ≤ 40). Вторая строка содержит N целых чисел l1, l2, …, lN (1 ≤ lN ≤ 100) — длины прямолинейных участков.

Формат вывода
Выведите одно целое неотрицательное число — наименьшую возможную разность периметров. Если построить две кольцевые монорельсовые линии нельзя, выведите -1.

Пример 1
Ввод Вывод
6
4 4 5 4 4 4
1
Пример 2
Ввод Вывод
7
3 2 1 1 2 3 2
0
Пример 3
Ввод Вывод
6
1 1 1 1 1 10
-1

asn85    2   04.06.2020 19:28    147