← 返回题目列表

Codeforces · 837/D

D. 圆形子集

中文机器翻译题面 查看原题

我们将数字的圆度称为它结尾的零的数量。

你有一个由 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。