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.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        FastScanner in = new FastScanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        new Main().run(in, out);
        out.close();
    }

    public static long mod = 17352642619633L;

    void run(FastScanner in, PrintWriter out) {
        int N = in.nextInt();
        int K = in.nextInt();

        // number of 2s, number of 5s
        int[][] a = new int[N][2];
        for (int i = 0; i < N; i++) {
            long n = in.nextLong();
            int twoCnt = 0;
            int fiveCnt = 0;
            while (n%2 == 0) {
                twoCnt++;
                n >>= 1;
            }
            while (n%5 == 0) {
                fiveCnt++;
                n/=5;
            }
            a[i][0] = twoCnt;
            a[i][1] = fiveCnt;
        }

        // i/k/j = max power of 2 can reach with power j,
        // picking k elements of the first i

        int max5 = 200*25;
        int[][][] dp = new int[2][K+1][max5+1];
        for (int[][] dd : dp) for (int[] d : dd) Arrays.fill(d, -1);
        dp[0][0][0] = 0;

        for (int i = 0; i < N; i++) {

            for (int k = 0; k <= K; k++) {

                for (int pow5 = 0; pow5 <= max5; pow5++) {
                    // can take or skip
                    dp[(i+1)%2][k][pow5] = Math.max(dp[(i+1)%2][k][pow5], dp[i%2][k][pow5]);

                    // take
                    if (k+1 <= K && dp[i%2][k][pow5] != -1) {
                        dp[(i+1)%2][k+1][pow5+a[i][1]] =
                            Math.max(dp[(i+1)%2][k+1][pow5+a[i][1]],
                                    dp[i%2][k][pow5]+a[i][0]);
                    }

                }

            }

        }

        int max = 0;
        // dp[N%2][K][any]
        for (int i = 0; i <= max5; i++) {
            max = Math.max(max, Math.min(dp[N%2][K][i], i));
        }
        out.println(max);
    }

    static class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        public FastScanner(InputStream in) {
            br = new BufferedReader(new InputStreamReader(in));
            st = null;
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }
    }
}
