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

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        TaskD solver = new TaskD();
        solver.solve(1,in);
    }

    static class TaskD {
        public int f(long x, int d) {
            int c = 0;
            while (x % d == 0) {
                x /= d;
                c++;
            }
            return c;
        }

        public void solve(int testNumber,Scanner in) {
            
            int n = in.nextInt(), k = in.nextInt();
            long[] arr = new long [n];
            for(int i=0;i<n;i++){
                arr[i]=in.nextLong();
            }
            int[] n2 = new int[n], n5 = new int[n];
            for (int i = 0; i < n; i++) {
                n2[i] = f(arr[i], 2);
                n5[i] = f(arr[i], 5);
            }

            int sall = AUtils.sum(n5);
            int[][] dp = new int[k + 1][sall + 1];
            for (int[] x : dp) Arrays.fill(x, -(1 << 29));
            dp[0][0] = 0;
            for (int i = 0; i < n; i++) {
                for (int c = k; c >= 1; c--) {
                    for (int d = n5[i]; d <= sall; d++) {
                        dp[c][d] = Math.max(dp[c][d], dp[c - 1][d - n5[i]] + n2[i]);
                    }
                }
            }

            int best = 0;
            for (int i = 0; i <= sall; i++) {
                best = Math.max(best, Math.min(i, dp[k][i]));
            }
            System.out.println(best);
        }

    }

    static class AUtils {
        public static int sum(int[] arr) {
            int sum = 0;
            for (int x : arr) {
                sum += x;
            }
            return sum;
        }

    }
}