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.File;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.PrintStream;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

/*
 public class _837D {

 }

 */

public class _837D
{
	public void solve() throws FileNotFoundException
	{
		InputStream inputStream = System.in;

		InputHelper inputHelper = new InputHelper(inputStream);

		PrintStream out = System.out;

		// actual solution
		int n = inputHelper.readInteger();
		int k = inputHelper.readInteger();

		long[] a = new long[n];

		int[] a2 = new int[n];
		int[] a5 = new int[n];

		for (int i = 0; i < n; i++)
		{
			a[i] = inputHelper.readLong();

			long ca = a[i];

			while (ca % 2 == 0)
			{
				ca /= 2;
				a2[i]++;
			}

			while (ca % 5 == 0)
			{
				ca /= 5;
				a5[i]++;
			}
		}

		int[][][] dp = new int[2][n][26 * k + 1];

		for (int j = 0; j < n; j++)
		{
			for (int l = 1; l <= 26 * k; l++)
			{
				dp[0][j][l] = Integer.MIN_VALUE;
			}
		}

		for (int i = 0; i < n; i++)
		{
			dp[0][i][a5[i]] = Math.max(dp[0][i][a5[i]], a2[i]);
		}

		for (int j = 0; j < n; j++)
		{
			for (int l = 0; l <= 26 * k; l++)
			{
				if (j > 0)
					dp[0][j][l] = Math.max(dp[0][j][l], dp[0][j - 1][l]);
			}
		}

		for (int i = 1; i < k; i++)
		{
			for (int j = 0; j < n; j++)
			{
				for (int l = 1; l <= 26 * k; l++)
				{
					dp[i & 1][j][l] = Integer.MIN_VALUE;
				}
			}

			for (int j = i; j < n; j++)
			{
				for (int l = 0; l <= 26 * k; l++)
				{
					if (l >= a5[j])
						dp[i & 1][j][l] = Math.max(dp[i & 1][j][l],
								dp[(i + 1) & 1][j - 1][l - a5[j]] + a2[j]);

					dp[i & 1][j][l] = Math.max(dp[i & 1][j][l],
							dp[i & 1][j - 1][l]);
				}
			}
		}

		int ans = 0;

		for (int l = 0; l <= 26 * k; l++)
		{
			int max2pow = dp[(k - 1) & 1][n - 1][l];

			ans = Math.max(ans, Math.min(l, max2pow));
		}

		System.out.println(ans);
		// end here
	}

	public static void main(String[] args) throws FileNotFoundException
	{
		(new _837D()).solve();
	}

	class InputHelper
	{
		StringTokenizer tokenizer = null;
		private BufferedReader bufferedReader;

		public InputHelper(InputStream inputStream)
		{
			InputStreamReader inputStreamReader = new InputStreamReader(
					inputStream);
			bufferedReader = new BufferedReader(inputStreamReader, 16384);
		}

		public String read()
		{
			while (tokenizer == null || !tokenizer.hasMoreTokens())
			{
				try
				{
					String line = bufferedReader.readLine();
					if (line == null)
					{
						return null;
					}
					tokenizer = new StringTokenizer(line);
				}
				catch (IOException e)
				{
					e.printStackTrace();
				}
			}

			return tokenizer.nextToken();
		}

		public Integer readInteger()
		{
			return Integer.parseInt(read());
		}

		public Long readLong()
		{
			return Long.parseLong(read());
		}
	}
}