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 _837D {
    static int[] MODS = {1000000007, 998244353, 1000000009};
    static int MOD = MODS[0];
    static int n, k;
    static int[][] nums;
    static long[] arr;
    static int[][][] dp;

    public static void main(String[] args) {
        sc = new MyScanner();
        out = new PrintWriter(new BufferedOutputStream(System.out));
        n = sc.nextInt();
        k = sc.nextInt();
        arr = new long[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextLong();
        }
        nums = new int[n+1][2];
        for (int i = 0; i < n; i++) {
            long x = arr[i];
            while (x % 2 == 0) {
                x /= 2;
                nums[i][0]++;
            }
            x = arr[i];
            while (x % 5 == 0) {
                x /= 5;
                nums[i][1]++;
            }
        }
        dp = new int[2][n+1][26*n];
        dp[1][1][nums[0][1]] = nums[0][0]+1;
        dp[1][0][0] = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= n; j++) {
                for (int k = 0; k < 26*n; k++) {
                    dp[0][j][k] = dp[1][j][k];
                }
            }
            for (int j = 1; j <= n; j++) {
                for (int k = 0; k < 26*n; k++) {
                    if (k >= nums[i][1] && dp[0][j-1][k-nums[i][1]] != 0) {
                        dp[1][j][k] = Math.max(dp[1][j][k], dp[0][j-1][k-nums[i][1]]+nums[i][0]);
                    }
                    if (dp[0][j][k] != 0) {
                        dp[1][j][k] = Math.max(dp[1][j][k], dp[0][j][k]);
                    }
                }
            }
        }
        int max = 0;
        for (int i = 0; i < 26*n; i++) {
            max = Math.max(max, Math.min(i, dp[1][k][i]-1));
        }
        out.println(max);
        out.close();
    }

    public static int[] sort(int[] arr) {
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            list.add(arr[i]);
        }
        Collections.sort(list);
        for (int i = 0; i < arr.length; i++) {
            arr[i] = list.get(i);
        }
        return arr;
    }

    public static void scan(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            arr[i] = sc.nextInt();
        }
    }

    public static MyScanner sc;
    public static PrintWriter out;

    public static class MyScanner {
        BufferedReader br;
        StringTokenizer st;

        public MyScanner() {
            br = new BufferedReader(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;
        }
    }
}
