Назовем круглостью числа количество нулей, которым оно оканчивается.
Задан массив из n чисел. Выберите такое подмножество из ровно k чисел, чтобы круглость произведения выбранных чисел была максимальна. Выведите полученное значение круглости.
Выходные данные
Выведите максимальную круглость произведения подмножества из k чисел.
Примечание
В первом примере есть три подмножества из 2 чисел. У подмножества [50, 4] произведение 200, круглость — 2, [4, 20] — произведение 80, круглость 1, [50, 20] — произведение 1000, круглость 3.
Во втором примере у подмножества [15, 16, 25] произведение — 6000, круглость — 3.
В третьем примере произведения всех подмножеств имеют круглость 0.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
50 4 20
|
3
|
|
2
|
5 3
15 16 3 25 9
|
3
|
|
3
|
3 3
9 77 13
|
0
|