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

public class RoundSubset {
	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());
		int[][] factors = new int[n][2];

		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < n; i++) {
			long a = Long.parseLong(st.nextToken());
			
			for(long j = a; j % 2 == 0; j /= 2) factors[i][0]++;
			for(long j = a; j % 5 == 0; j /= 5) factors[i][1]++;
		}
		br.close();
		
		long[][] dp = new long[k+1][(26 * n) + 1];
		for(int j = 0; j <= k; j++) Arrays.fill(dp[j], -1);
		
		dp[0][0] = 0;
		for(int i = 1; i <= n; i++) { // n
			int two = factors[i-1][0], five = factors[i-1][1];
			//System.out.println("i: " + two + " " + five);
			for(int j = Math.min(i, k); j > 0; j--) { // k
				
				for(int f = (26 * n); f >= five ; f--) { // fives
					//System.out.println("j: " + j + " f: " + f);
					if(dp[j-1][f-five] != -1)
					dp[j][f] = Math.max(dp[j][f], dp[j-1][f - five] + two);
				}
			}
		}
		
		long res = 0;
		for(int f = 0; f <= 26 * n; f++) res = Math.max(res, Math.min(f, dp[k][f]));
		System.out.println(res);
	}
}