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.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.Reader;
import java.util.ArrayList;
import java.util.Objects;
import java.util.StringTokenizer;

public class D2 {

    private static final long MODULO = (long) (1e9 + 7);
    private static int n, k;
    static long[] a;
    static int[] ten, twoFive;

    public static void main(String[] args) {
        BufferedScanner scanner = new BufferedScanner();
        PrintWriter writer = new PrintWriter(new BufferedOutputStream(System.out));

        int t = 1;//scanner.nextInt();
        for (int tc = 0; tc < t; tc++) {
            n = scanner.nextInt();
            k = scanner.nextInt();
            a = new long[n];
            ten = new int[n];
            twoFive = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = scanner.nextLong();
                while (a[i] % 10 == 0) {
                    ten[i]++;
                    a[i] /= 10;
                }
                while (a[i] % 2 == 0) {
                    twoFive[i]++;
                    a[i] /= 2;
                }
                while (a[i] % 5 == 0) {
                    twoFive[i]--;
                    a[i] /= 5;
                }
            }

            int[][][] dp1 = new int[2][k + 1][n * 60 + 1], dp2 = new int[2][k + 1][n * 60 + 1];
            System.err.println(Objects.hashCode(dp1) + " " + Objects.hashCode(dp2));
            for (int which = n; which >= 0; which--) {
                {
                    int[][][] tmp = dp2;
                    dp2 = dp1;
                    dp1 = tmp;
//                    System.err.println(Objects.hashCode(dp1) + " " + Objects.hashCode(dp2));
//                    for (int type = 0; type < 2; type++) {
//                        for (int chosen = 0; chosen <= k; chosen++) {
//                            for (int twoFiveAcc = 0; twoFiveAcc <= which * 60; twoFiveAcc++) {
//                                dp1[type][chosen][twoFiveAcc] = -1;
//                            }
//                        }
//                    }
                }

                for (int chosen = 0; chosen <= Math.min(which, k); chosen++) {
                    for (int twoFiveAcc = -which * 60; twoFiveAcc <= which * 60; twoFiveAcc++) {
                        int type = twoFiveAcc >= 0 ? 0 : 1;
                        if (chosen == k || which == n) {
                            dp1[type][chosen][Math.abs(twoFiveAcc)] = 0;
                            continue;
                        }
                        if (k - chosen > n - which) {
                            dp1[type][chosen][Math.abs(twoFiveAcc)] = 0;
                            continue;
                        }

                        int ans = dp2[type][chosen][Math.abs(twoFiveAcc)];

                        int two = Math.max(twoFiveAcc, 0);
                        int five = Math.max(-twoFiveAcc, 0);
                        if (twoFive[which] > 0) {
                            two += twoFive[which];
                        } else {
                            five -= twoFive[which];
                        }
                        int newTen = ten[which] + Math.min(two, five);
                        int newTwoFiveAcc = two - five;
                        int newType = newTwoFiveAcc >= 0 ? 0 : 1;
                        ans = Math.max(ans, newTen + dp2[newType][chosen + 1][Math.abs(newTwoFiveAcc)]);

                        dp1[type][chosen][Math.abs(twoFiveAcc)] = ans;
//                        System.err.println(ans);
                    }
                }
            }
            writer.println(dp1[0][0][0]);
        }

        scanner.close();
        writer.flush();
        writer.close();
    }

    static class ListInt extends ArrayList<Integer> {}

    public static class BufferedScanner {
        BufferedReader br;
        StringTokenizer st;

        public BufferedScanner(Reader reader) {
            br = new BufferedReader(reader);
        }

        public BufferedScanner() {
            this(new InputStreamReader(System.in));
        }

        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());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

        void close() {
            try {
                br.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }

    }

    static long gcd(long a, long b) {
        if (a < b) {
            return gcd(b, a);
        }
        while (b > 0) {
            long tmp = b;
            b = a % b;
            a = tmp;
        }
        return a;
    }

    static long inverse(long a, long m) {
        long[] ans = extgcd(a, m);
        return ans[0] == 1 ? (ans[1] + m) % m : -1;
    }

    private static long[] extgcd(long a, long m) {
        if (m == 0) {
            return new long[]{a, 1, 0};
        } else {
            long[] ans = extgcd(m, a % m);
            long tmp = ans[1];
            ans[1] = ans[2];
            ans[2] = tmp;
            ans[2] -= ans[1] * (a / m);
            return ans;
        }
    }

    static long add(long a, long b) {
        a += b;
        if (a >= MODULO) {
            a -= MODULO;
        }
        return a;
    }

    static long sub(long a, long b) {
        a -= b;
        if (a < 0) {
            a += MODULO;
        }
        return a;
    }

    static long mul(long a, long b) {
        return a * b % MODULO;
    }

    static long div(long a, long b) {
        return a * inverse(b, MODULO) % MODULO;
    }

    static class Comb {
        final long modulo;
        final long[] fac, fnv;

        Comb(int limit, long modulo) {
            fac = new long[limit + 1];
            fnv = new long[limit + 1];
            fac[0] = 1;
            fnv[0] = 1;
            for (int i = 1; i <= limit; i++) {
                fac[i] = mul(fac[i - 1], i);
                fnv[i] = div(fnv[i - 1], i);
            }
            this.modulo = modulo;
        }

        long c(int total, int choose) {
            if (total < choose) {
                return 0;
            }
            if (total == 0 || total == choose) {
                return 1;
            }
            return mul(mul(fac[total], fnv[choose]), fnv[total - choose]);
        }
    }

}
