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 {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), k = in.nextInt();
        in.nextLine();
        int[] a2 = new int[n];
        for (int i = 0; i < n; i++) {
            a2[i] = 0;
        }
        int[] a5 = new int[n];
        for (int i = 0; i < n; i++) {
            a5[i] = 0;
        }
        for (int i = 0; i < n; i++) {
            long number = in.nextLong();
            while (number % 2 == 0) {
                number = number / 2;
                a2[i] = a2[i] + 1;
            }
            while (number % 5 == 0) {
                number = number / 5;
                a5[i] = a5[i] + 1;
            }
        }
        int[][] f = new int[k][12000];
        for (int i = 0; i < k; i++) {
            for (int j = 0; j < 12000; j++) {
                f[i][j] = -1;
            }
        }
        for (int i = 0; i < n; i++) {
            int limit = Math.min(i, k - 1);
            for (int j = limit; j > 0; j--) {
                for (int l = a2[i]; l < 12000; l++) {
                    if ((f[j - 1][l - a2[i]] != -1 ) && (f[j][l] < f[j - 1][l - a2[i]] + a5[i]))
                        f[j][l] = f[j - 1][l - a2[i]] + a5[i];
                }
            }
            if (a5[i] > f[0][a2[i]])
                f[0][a2[i]] = a5[i];
        }
        int max = 0;
        for (int i = 11999; i >= 0; i--) {
            if (f[k - 1][i] != -1) {
                if (Math.min(i, f[k - 1][i]) > max) {
                    max = Math.min(i, f[k - 1][i]);
                }
            }
        }
        System.out.print(max);
    }



}
