e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Problems

Сложите многоугольник

Сложите многоугольник

Задан набор отрезков. Какое наименьшее число отрезков надо удалить из набора, чтобы из оставшегося числа отрезков можно было сложить многоугольник, используя отрезки в качестве его сторон. Многоугольник должен иметь ненулевую площадь.

Входные данные

В первой строке входного файла записано целое число n (3n50), где n – количество отрезков в наборе. Вторая строка содержит длины отрезков – последовательность длины n целых чисел, каждое из которых от 1 до 106 включительно.

Выходные данные

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

Time limit 4 seconds
Memory limit 64 MiB
Input example #1
4
1 1 1 100
Output example #1
1