Задачи
Сложите многоугольник
Сложите многоугольник
Задан набор отрезков. Какое наименьшее число отрезков надо удалить из набора, чтобы из оставшегося числа отрезков можно было сложить многоугольник, используя отрезки в качестве его сторон. Многоугольник должен иметь ненулевую площадь.
\InputFile
В первой строке входного файла записано целое число \textbf{n} (\textbf{3} ≤ \textbf{n} ≤ \textbf{50}), где \textbf{n} -- количество отрезков в наборе. Вторая строка содержит длины отрезков -- последовательность длины \textbf{n} целых чисел, каждое из которых от \textbf{1} до \textbf{10^6} включительно.
\OutputFile
Выведите наименьшее количество отрезков, которых надо удалить из заданного набора, чтобы из оставшегося числа отрезков было возможно сложить многоугольник. Если из любого поднабора отрезков сложить многоугольник невозможно, выведите \textbf{-1}.
Входные данные #1
4 1 1 1 100
Выходные данные #1
1