题目描述

我们把一个数的 $6$-roundness 值定义为它在 $6$ 进制下末尾 $0$ 的个数。

给你一个长度为 $n$ 的数列，要求你从中选出 $k$ 个数，使得这些选出的数的积的 $6$-roundness 值最大。

输入格式

第一行包括两个正整数 $n$ 和 $k$。

第二行包括 $n$ 个空白分隔的数 $a_1, a_2, \dots, a_n$。

输出格式

输出一个整数，是选择 $k$ 个数并作积的最大 $6$-roundness 值。

3 2
18 4 12

3

5 3
9 16 3 9 9

4

3 3
9 77 13

0

提示

【样例 1 解释】

在第一个例子中，有三种选法。

$\{18, 4\}$ 的积是 $(200)_6$，$6$-roundness 值是 $2$；

$\{4, 12\}$ 的积是 $(120)_6$，$6$-roundness 值是 $1$；

$\{18, 12\}$ 的积是 $(1000)_6$，$6$-roundness 值是 $3$。

【样例 2 解释】

第二个例子中选法 $\{9, 16, 9\}$ 的积是 $(10000)_6$，$6$-roundness 值是 $4$。

【样例 3 解释】

第三个例子中所有的选法的积的 $6$-roundness 值都是 $0$。

【子任务】

对于 $100\%$ 的数据，$1 \leq n \leq 200$，$1 \leq k \leq 100$，$2 \leq a_i \leq 10^9$。