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.lang.*;
import java.io.*;
import java.util.*;
import java.math.*;
import java.net.*;

import static java.lang.Math.*;

public class Solution implements Runnable {
    
    class Power implements Comparable<Power> {
        int p2, p5;

        public Power(int p2, int p5) {
            this.p2 = p2;
            this.p5 = p5;
        }

        @Override
        public int compareTo(Power p) {
            int c1 = p5 - p2;
            int c2 = p.p5 - p.p2;
            return c2 - c1;
        }
    }
    
    void solve() throws Exception {
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[][] dp = new int[k + 1][6000];
        Power[] p = new Power[n];
        for (int i = 0; i < n; i++) {
            long x = sc.nextLong();
            int p2 = 0, p5 = 0;
            while (x % 2 == 0) {
                p2++;
                x /= 2;
            }
            while (x % 5 == 0) {
                p5++;
                x /= 5;
            }
            p[i] = new Power(p2, p5);
        }
        Arrays.sort(p);
        for (int i = 0; i < k + 1; i++) {
            Arrays.fill(dp[i], -1);
        }
        dp[0][0] = 0;
        for (int id = 0; id < n; id++) {
            for (int i = min(k - 1, id); i >= 0; --i) {
                for (int j = 0; j < 6000; j++) {
                    if (dp[i][j] != -1) {
                        int add = min(j + p[id].p5, p[id].p2);
                        dp[i + 1][j + p[id].p5 - add] = max(dp[i + 1][j + p[id].p5 - add], dp[i][j] + add);
                    }
                }
            }
        }
        int mx = 0;
        for (int i = 0; i < 6000; i++) {
            mx = max(mx, dp[k][i]);
        }
        out.println(mx);
    }

    BufferedReader in;
    PrintWriter out;
    FastScanner sc;

    final String INPUT_FILE = "";
    final String OUTPUT_FILE = "";

    static Throwable throwable;

    public static void main(String[] args) throws Throwable {
        Thread thread = new Thread(null, new Solution(), "", (1 << 26));
        thread.start();
        thread.join();
        thread.run();
        if (Solution.throwable != null)
            throw Solution.throwable;
    }

    public void run() {
        try {
            if (INPUT_FILE.equals("")) {
                in = new BufferedReader(new InputStreamReader(System.in));
            } else {
                in = new BufferedReader(new FileReader(INPUT_FILE));
            }
            if (OUTPUT_FILE.equals("")) {
                out = new PrintWriter(System.out);
            } else {
                out = new PrintWriter(OUTPUT_FILE);
            }
            sc = new FastScanner(in);
            solve();
        } catch (Exception e) {
            throwable = e;
        } finally {
            out.close();
        }
    }

}

class FastScanner {
	
    BufferedReader reader;
    StringTokenizer strTok;

    FastScanner(BufferedReader reader) {
        this.reader = reader;
    }

    public String nextToken() throws Exception {
        while (strTok == null || !strTok.hasMoreTokens()) {
            strTok = new StringTokenizer(reader.readLine());
        }
        return strTok.nextToken();
    }

    public int nextInt() throws Exception {
        return Integer.parseInt(nextToken());
    }

    public double nextDouble() throws Exception {
        return Double.parseDouble(nextToken());
    }

    public long nextLong() throws Exception {
        return Long.parseLong(nextToken());
    }
}