题目描述

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

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

输入格式

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

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

输出格式

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

输入输出样例 #1

输入 #1

3 2
18 4 12

输出 #1

3

输入输出样例 #2

输入 #2

5 3
9 16 3 9 9

输出 #2

4

输入输出样例 #3

输入 #3

3 3
9 77 13

输出 #3

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$。

【子任务】

::cute-table{tuack} | 测试点编号 | $n$ | $k$ | $a_i$ | |:-:|:-:|:-:|:-:| | $1 \sim 2$ | $\leq 200$ | $\leq 100$ | 一定可以被表示为 $6$ 的幂次 | | $3$ | ^ | ^ | 在 $\{2, 3, 6\}$ 中取值 | | $4$ | $= 10$ | $= 5$ | 任意 $k$ 个 $a_i$ 之积不超过 $10^{18}$ | | $5$ | $= 25$ | $= 12$ | 只含有质因子 $2$ 或质因子 $3$ | | $6$ | ^ | ^ | 只含有质因子 $2$ 和质因子 $3$ | | $7$ | ^ | ^ | 无限制 | | $8$ | $\leq 200$ | $\leq 100$ | ^ | | $9$ | ^ | ^ | ^ | | $10$ | ^ | ^ | ^ |

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