Вам задана последовательность положительных целых чисел a1, a2, ..., an. Все числа в последовательности различны. Зафиксируем набор переменных b1, b2, ..., bm. Изначально в каждой переменной bi (1 ≤ i ≤ m) хранится значение нуль. Рассмотрим следующую последовательность, состоящую из n операций.
Первая операция состоит в том, чтобы присвоить какой-то переменной bx (1 ≤ x ≤ m) значение, равное a1. Каждая из следующих n - 1 операций состоит в том, чтобы присвоить какой-то переменной by значение, равное сумме значений, хранящихся в переменных bi и bj (1 ≤ i, j, y ≤ m). При этом значение, которое присваивается на t-ой операции, должно быть равно at. Для каждой операции числа y, i, j выбираются заново.
Вам требуется найти минимальное количество переменных m такое, что с помощью этих переменных можно произвести описанную последовательность операций.
Выходные данные
В единственной строке выведите целое число — минимальное количество переменных m такое, что с помощью этих переменных можно произвести описанную последовательность операций.
Если ни при каком значении m выполнить последовательность операций нельзя, выведите -1.