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.*;
import java.util.*;
import java.math.*;
import java.util.concurrent.*;

public final class round
{
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	static FastScanner sc=new FastScanner(br);
    static PrintWriter out=new PrintWriter(System.out);
	static Random rnd=new Random();
	static int maxn;
		
    public static void main(String args[]) throws Exception
    {
		int n=sc.nextInt(),K=sc.nextInt();long[] c=new long[n];int[] a=new int[n],b=new int[n];
		
		for(int i=0;i<n;i++)
		{
			c[i]=sc.nextLong();
		}
		
		for(int i=0;i<n;i++)
		{
			long curr=c[i];
			
			while(curr>0 && curr%5==0)
			{
				curr/=5;a[i]++;
			}
			
			curr=c[i];
			
			while(curr>0 && curr%2==0)
			{
				curr/=2;b[i]++;
			}
		}
		
		maxn=n*27;int[][][] dp=new int[2][K+1][maxn];
		
		for(int i=0;i<2;i++)
		{
			for(int j=0;j<=K;j++)
			{
				for(int k=0;k<maxn;k++)
				{
					dp[i][j][k]=-1;
				}
			}
		}
		
	//	out.println(Arrays.toString(a)+" "+Arrays.toString(b));
		
		dp[0][1][a[0]]=b[0];dp[0][0][0]=0;int sum=0;
		
		for(int i=1,x=1;i<n;i++,x=1^x)
		{
			for(int j=0;j<=K;j++)
			{
				for(int k=0;k<maxn;k++)
				{
					dp[x][j][k]=Math.max(dp[x][j][k],dp[x^1][j][k]);
					
					if(k>=a[i] && j>0 && dp[x^1][j-1][k-a[i]]!=-1)
					{
						dp[x][j][k]=Math.max(dp[x][j][k],dp[x^1][j-1][k-a[i]]+b[i]);
					}
				}
			}
		}
		
	//	out.println(dp[2][2][3]);
		
		int max=-1;
		
		for(int j=0;j<maxn;j++)
		{
			int val1=Math.min(dp[0][K][j],j),val2=Math.min(dp[1][K][j],j);
			
			max=Math.max(max,Math.max(val1,val2));
		}
		
		out.println(max);out.close();
    }
}
class FastScanner
{
    BufferedReader in;
    StringTokenizer st;

    public FastScanner(BufferedReader in) {
        this.in = in;
    }
	
    public String nextToken() throws Exception {
        while (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(in.readLine());
        }
        return st.nextToken();
    }
	
	public String next() throws Exception {
		return nextToken().toString();
	}
	
    public int nextInt() throws Exception {
        return Integer.parseInt(nextToken());
    }

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

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