На доске написаны \(n\) целых положительных чисел \(a_1, a_2, \dots, a_n\). Вам также дано целое положительное число \(k\). Вы можете выполнить следующую операцию несколько (возможно, \(0\)) раз:
- выбрать на доске число \(x\);
- стереть одно вхождение \(x\);
- написать на доске два положительных целых числа \(y\), \(z\) таких, что \(y+z = x+k\).
Можно ли сделать так, чтобы все числа на доске стали равны? Если да, то какое минимальное количество операций вам потребуется?
Выходные данные
Для каждого набора входных данных выведите одну строку, содержащую целое число: минимальное количество операций, необходимых для того, чтобы все числа на доске стали равными, или \(-1\), если это невозможно.
Примечание
В первом наборе входных данных \(k = 1\). Вы можете сделать все числа на доске равными \(2\) с помощью следующих операций:
- Стереть \(x = 4\) и написать \((y, z) = (2, 3)\). Обратите внимание, что \(y+z=x+k\). Теперь на доске написано мультимножество \(\{3, 2, 3\}\).
- Стереть \(x = 3\) и написать \((y, z) = (2, 2)\). Заметьте, что \(y+z=x+k\). Теперь на доске написано \(\{2, 2, 2, 3\}\).
- Стереть \(x = 3\) и написать \((y, z) = (2, 2)\). Заметьте, что \(y+z=x+k\). Теперь на доске написано \(\{2, 2, 2, 2, 2\}\).
Это делает все числа равными за \(3\) операции. Можно показать, что нельзя сделать все числа равными менее чем за \(3\) операции.
Во втором наборе входных данных \(k = 3\). Вы можете сделать все числа на доске равными \(7\) с помощью следующей операции:
- Стереть \(x = 11\) и написать \((y, z) = (7, 7)\). Обратите внимание, что \(y+z=x+k\). Теперь на доске написано \(\{7, 7, 7\}\).
В третьем наборе входных данных \(k = 10\). Вы можете сделать все числа на доске равными \(40\) с помощью следующих операций:
- Стереть \(x = 100\) и написать \((y, z) = (70, 40)\). Обратите внимание, что \(y+z=x+k\). Теперь на доске написано \(\{70, 40, 40, 100\}\).
- Стереть \(x = 70\) и написать \((y, z) = (40, 40)\). Обратите внимание, что \(y+z=x+k\). Теперь на доске написано \(\{40, 40, 40, 40, 100\}\).
- Стереть \(x = 100\) и написать \((y, z) = (40, 70)\). Заметьте, что \(y+z=x+k\). Теперь на доске написано \(\{40, 40, 40, 40, 40, 70\}\).
- Стереть \(x = 70\) и написать \((y, z) = (40, 40)\). Заметьте, что \(y+z=x+k\). Теперь на доске написано \(\{40, 40, 40, 40, 40, 40, 40\}\).
В четвертом и пятом наборе входных данных можно показать, что невозможно сделать все числа на доске одинаковыми.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
9
2 1
3 4
2 3
7 11
3 10
100 40 100
2 1
1 2
2 2
1 2
1 327869541
327869541
5 26250314066
439986238782 581370817372 409476934981 287439719777 737637983182
5 616753575719
321037808624 222034505841 214063039282 441536506916 464097941819
5 431813672576
393004301966 405902283416 900951084746 672201172466 518769038906
|
3
1
4
-1
-1
0
3119
28999960732
-1
|