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.
#include <bits/stdc++.h>
using namespace std;
const int N = 201;
const int inf = 70 * N;
int n, k, a[N][2], f[N][N * 18];
template <class T>
inline void cmax(T& x, T y) {
  if (y > x) x = y;
}
int main() {
  int i, j, t;
  scanf("%d%d", &n, &k);
  for (i = 1; i <= n; ++i) {
    long long x, y;
    scanf("%I64d", &x);
    for (y = x; !(x & 1LL); x >>= 1) ++a[i][0];
    for (x = y; !(x % 5LL); x /= 5LL) ++a[i][1];
  }
  int T = 18 * n;
  for (j = 0; j <= k; ++j)
    for (t = 0; t <= T; ++t) f[j][t] = -inf;
  f[0][0] = 0;
  for (i = 1; i <= n; ++i) {
    for (j = k; j; --j) {
      for (t = max(0, T - a[i][1]); t <= T; ++t) {
        cmax(f[j][T], f[j - 1][t] + a[i][0]);
      }
      for (t = T; t >= a[i][1]; --t) {
        cmax(f[j][t], f[j - 1][t - a[i][1]] + a[i][0]);
      }
    }
  }
  int ans = 0;
  for (t = 0; t <= T; ++t) cmax(ans, min(f[k][t], t));
  printf("%d", ans);
  return 0;
}
