我们将数字的圆度称为它结尾的零的数量。
你有一个由 n 个数字组成的数组。您需要选择恰好 k 个数字的子集,以便所选数字的乘积的圆度尽可能最大。
输入
第一行包含两个整数 n 和 k (1 ≤ n ≤ 200, 1 ≤ k ≤ n)。
第二行包含 n 个空格分隔的整数 a1, a2, ..., an (1 ≤ ai ≤ 1018)。
输出
打印所选长度 k 子集的乘积的最大圆度。
示例
输入 #1
3 2 50 4 20
输出 #1
3
输入 #2
5 3 15 16 3 25 9
输出 #2
3
输入 #3
3 3 9 77 13
输出 #3
0
注意
在第一个示例中,有 2 个数字的 3 个子集。 [50, 4] 的产品 200,圆度 2,[4, 20] — 产品 80,圆度 1,[50, 20] — 产品 1000,圆度 3。
在第二个示例中,子集 [15,16,25] 的乘积为 6000,圆度为 3。
在第三个示例中,所有子集的乘积的圆度均为 0。