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.util.Scanner;

public class Main {

    private static final int DIV5 = 5000;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        int[] twos = new int[n];
        int[] fives = new int[n];

        for (int i=0; i<n; i++) {
            long l = in.nextLong();
            twos[i] = getDivision(l, 2);
            fives[i] = getDivision(l, 5);
        }

        int[][][] dp = new int[2][k+1][DIV5+1];

        for (int j=0; j<k; j++) {
            for (int l=0; l<=DIV5; l++) {
                dp[0][j][l] = -1;
                dp[1][j][l] = -1;
            }
        }
        dp[0][1][fives[0]] = twos[0];

        for (int i=1; i<n; i++) {
            int cur = i % 2;
            int prev = (i+1) % 2;
            for (int j=1; j<=k; j++) {
                for (int l=0; l<=DIV5; l++) {
                    dp[cur][j][l] = dp[prev][j][l];
                    if (l-fives[i] >= 0) {
                        dp[cur][j][l] = Math.max(dp[prev][j][l],
                                (dp[prev][j - 1][l - fives[i]] >= 0) ? dp[prev][j - 1][l - fives[i]] + twos[i] : -1
                        );
                    }
                }
                if (j == 1) {
                    dp[cur][j][fives[i]] = Math.max(dp[cur][1][fives[i]], twos[i]);
                }
            }
        }
        int res = 0;
        for (int l = 0; l <= DIV5; l++) {
            res = Math.max(res, Math.min(l, dp[(n-1) % 2][k][l]));
        }

        System.out.print("" + res);
    }

    private static int getDivision(long l, int f) {
        int res = 0;
        while (l >= f) {
            if (l % f != 0) break;
            res += 1;
            l /= f;
        }
        return res;
    }

}
