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.
/*/*
 * Author Ayub Subhaniya
 * Institute DA-IICT
 */

import java.io.*;
import java.util.*;

public class  Educational21 {
	
	InputStream in;
	PrintWriter out;
	
	
	void solve() {
		int n=ni();
		int k=ni();
		Pair p[]=new Pair[n];
		for (int i=0;i<n;i++)
		{
			long num=nl();
			int twos,fives;
			twos=fives=0;
			while (num%2==0)
			{
				twos++;
				num/=2;
			}
			while (num%5==0)
			{
				fives++;
				num/=5;
			}
			p[i]=new Pair(twos,fives);
		}
		int dp[][]=new int[k][26*n+1];
		for (int i=0;i<k;i++)
		Arrays.fill(dp[i], -1);
		for (int j=0;j<n;j++)
		{
			for (int i=k-1;i>0;i--)
			{
				for (int x=26*n-1;x>=0;x--)
					if (dp[i-1][x]!=-1)
						dp[i][x+p[j].y]=Math.max(dp[i][x+p[j].y],dp[i-1][x]+p[j].x);
			}
			dp[0][p[j].y]=Math.max(dp[0][p[j].y],p[j].x);
		}
		int max=0;
		for (int i=0;i<26*n;i++)
			max=Math.max(max,Math.min(i, dp[k-1][i]));
		out.println(max);
	}
	
	Pair max(Pair p1,Pair p2,Pair p3)
	{
		if (p1==null)
		{
			if (p2==null)
				return p3;
			else
				return new Pair(p2.x+p3.x,p2.y+p3.y);
		}
		else if (p2==null)
			return new Pair(Math.max(p1.x, p3.x),p1.y);
		else
			return new Pair(Math.max(p1.x, p2.x+p3.x),p1.y);
	}
	
	class Pair implements Comparable<Pair> {
		int x;
		int y;

		Pair(int a, int b) {
			x = a;
			y = b;
		}

		@Override
		public boolean equals(Object o) {
			Pair other = (Pair) o;
			return x == other.x && y == other.y;
		}

		public String toString() {
			return x + " " + y;
		}

		@Override
		public int compareTo(Pair o) {
			if (x == o.x)
				return Integer.compare(y, o.y);
			else
				return Integer.compare(x, o.x);
		}

		@Override
		public int hashCode() {
			return Objects.hash(x, y);
		}
	} 
			
	void run() throws Exception {
		String INPUT = "C:/Users/ayubs/Desktop/input.txt";
		in = oj ? System.in : new FileInputStream(INPUT);
		out = new PrintWriter(System.out);
		
			long s = System.currentTimeMillis();
			solve();
			out.flush();
			tr(System.currentTimeMillis() - s + "ms");
		
	}
	public static void main(String[] args) throws Exception {
		new Educational21().run();
	}
	
	private byte[] inbuf = new byte[1024];
	public int lenbuf = 0, ptrbuf = 0;
	
	private int readByte() {
		if (lenbuf == -1)
			throw new InputMismatchException();
		if (ptrbuf >= lenbuf) {
			ptrbuf = 0;
			try {
				lenbuf = in.read(inbuf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (lenbuf <= 0)
				return -1;
		}
		return inbuf[ptrbuf++];
	}
	
	private boolean inSpaceChar(int c) {
		return !(c >= 33 && c <= 126);
	}
	
	private int skip() {
		int b;
		while ((b = readByte()) != -1 && inSpaceChar(b))
			;
		return b;
	}
	
	private double nd() {
		return Double.parseDouble(ns());
	}
	
	private char nc() {
		return (char) skip();
	}
	
	private String ns() {
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while (!(inSpaceChar(b))) { // when nextLine, (inSpaceChar(b) && b != ' ')
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	
	private char[] ns(int n) {
		char[] buf = new char[n];
		int b = skip(), p = 0;
		while (p < n && !(inSpaceChar(b))) {
			buf[p++] = (char) b;
			b = readByte();
		}
		return n == p ? buf : Arrays.copyOf(buf, p);
	}
	
	private char[][] nm(int n, int m) {
		char[][] map = new char[n][];
		for (int i = 0; i < n; i++)
			map[i] = ns(m);
		return map;
	}
	
	private int[] na(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = ni();
		return a;
	}
	
	private int ni() {
		int num = 0, b;
		boolean minus = false;
		while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
			;
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		
		while (true) {
			if (b >= '0' && b <= '9') {
				num = num * 10 + (b - '0');
			} else {
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	private long nl() {
		long num = 0;
		int b;
		boolean minus = false;
		while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
			;
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		
		while (true) {
			if (b >= '0' && b <= '9') {
				num = num * 10 + (b - '0');
			} else {
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	private boolean oj = System.getProperty("ONLINE_JUDGE") != null;
	
	private void tr(Object... o) {
		if (!oj)
			System.out.println(Arrays.deepToString(o));
	}
	
}