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.*;

public class CF837D {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		int[] c2 = new int[n];
		int[] c5 = new int[n];
		for (int i = 0; i < n; i++) {
			long a = Long.parseLong(st.nextToken());
			int cnt;
			cnt = 0;
			for (long x = a; x % 2 == 0; x /= 2)
				cnt++;
			c2[i] = cnt;
			cnt = 0;
			for (long x = a; x % 5 == 0; x /= 5)
				cnt++;
			c5[i] = cnt;
		}
		int[] ss = Arrays.copyOf(c5, n);
		Arrays.sort(ss);
		int m5 = 0;
		for (int i = 1; i <= k; i++)
			m5 += ss[n - i];
		// dp[h][f]: maximum 2's of any h-subset with f 5's
		int[][] dp = new int[k + 1][m5 + 1];
		int[][] dq = new int[k + 1][m5 + 1];
		for (int h = 0; h <= k; h++)
			for (int f = 0; f <= m5; f++)
				dp[h][f] = -1;
		dp[0][0] = 0;
		for (int i = 0; i < n; i++) {
			for (int h = 0; h <= k; h++)
				for (int f = 0; f <= m5; f++)
					dq[h][f] = dp[h][f];
			for (int h = 0; h < k; h++)
				for (int f = 0; f <= m5; f++) {
					int t = dp[h][f];
					if (t >= 0) {
						int b2 = t + c2[i];
						int b5 = f + c5[i];
						dq[h + 1][b5] = Math.max(dq[h + 1][b5], b2);
					}
				}
			int[][] tmp = dp; dp = dq; dq = tmp;
		}
		int max = 0;
		for (int f = 0; f <= m5; f++) {
			int t = dp[k][f];
			max = Math.max(max, Math.min(f, t));
		}
		System.out.println(max);
	}
}
