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.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;


public class ED26D2
{
	static int cnt5[], cnt2[], dp[][][];
	static long[] arr;
	public static void main(String[] args) throws IOException
	{
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		arr = new long[n];
		cnt5 = new int[n];
		cnt2 = new int[n];
		
		for (int i = 0; i < n; i++)
			arr[i] = sc.nextLong();
		
		for (int i = 0; i < n; i++)
		{
			long num = arr[i];
			while(num % 2 == 0)
			{
				num = num/2;
				cnt2[i]++;
			}
			
			while(num % 5 == 0)
			{
				num = num/5;
				cnt5[i]++;
			}
		}
		
		int sum5 = 0;
		for (int i = 0; i < cnt5.length; i++)
			sum5 += cnt5[i];
		
		dp = new int[2][201][sum5+1];
		int p = 0;
		for (int i = 0; i < 201; i++)
			Arrays.fill(dp[p][i], -10000000);
		dp[p][0][0] = 0;
		for (int i = n-1; i >= 0; i--)
		{
			p = p^1;
			for (int rem = 0; rem <= k; rem++)
				for (int cnt = 0; cnt < sum5+1; cnt++)
				{
					dp[p][rem][cnt] = dp[p^1][rem][cnt];
					if(cnt >= cnt5[i] && rem > 0)
						dp[p][rem][cnt] = Math.max(dp[p][rem][cnt], cnt2[i] + dp[p^1][rem-1][cnt - cnt5[i]]);

				}
		}
		int ans = 0;
		for (int i = 0; i < sum5+1; i++)
			ans = Math.max(ans, Math.min(i, dp[p][k][i]));
		System.out.println(ans);
	}

	static class Scanner 
	{
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}
		public String next() throws IOException 
		{
			while (st == null || !st.hasMoreTokens()) 
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		public int nextInt() throws IOException {return Integer.parseInt(next());}
		public long nextLong() throws IOException {return Long.parseLong(next());}
		public String nextLine() throws IOException {return br.readLine();}
		public double nextDouble() throws IOException{return Double.parseDouble(next());}
		public boolean ready() throws IOException {return br.ready();}
	}
}
