Let's call the roundness of the number the number of zeros to which it ends.

You have an array of n numbers. You need to choose a subset of exactly k numbers so that the roundness of the product of the selected numbers will be maximum possible.

Input

The first line contains two integer numbers n and k (1 ≤ n ≤ 200, 1 ≤ k ≤ n).

The second line contains n space-separated integer numbers a1, a2, ..., an (1 ≤ ai ≤ 1018).

Output

Print maximal roundness of product of the chosen subset of length k.

Examples

Input

3 2
50 4 20


Output

3


Input

5 3
15 16 3 25 9


Output

3


Input

3 3
9 77 13


Output

0

Note

In the first example there are 3 subsets of 2 numbers. [50, 4] has product 200 with roundness 2, [4, 20] — product 80, roundness 1, [50, 20] — product 1000, roundness 3.

In the second example subset [15, 16, 25] has product 6000, roundness 3.

In the third example all subsets has product with roundness 0.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

// package dp;
public class roundset {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int[][] nums = new int[N][2];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            long c = Long.parseLong(st.nextToken());
            while (c % 2 == 0) {
                nums[i][0]++;
                c /= 2;
            }
            while (c % 5 == 0) {
                nums[i][1]++;
                c /= 5;
            }
        }
        int ret = 0;
        int[][] dp = new int[K + 1][30 * K]; //log(10^18)/log(5)
        for (int[] b : dp) {
            Arrays.fill(b, -6969420);
        }
        dp[K][0] = 0;
        for (int i = N - 1; i >= 0; i--) {
            int f = nums[i][1];
            int t = nums[i][0];
            for (int j = 0; j < K; j++) {
                for (int k = dp[j].length - 1; k >= 0; k--) {
                    if (k - f >= 0) {
                        dp[j][k] = Math.max(dp[j][k], dp[j + 1][k - f] + t);
                    }
                    ret = Math.max(ret, Math.min(k, dp[j][k]));
                }
            }
        }
        

        pw.println(ret);
        pw.close();
        br.close();
    }
}
