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;
long long n, k, i, j, l, nr2, nr5, nr, aux, d[210][3][12610], sol;
unsigned long long a;
int main() {
  cin >> n >> k;
  for (i = 0; i <= k; i++)
    for (j = 0; j <= 12600; j++) d[i][0][j] = d[i][1][j] = -1;
  d[0][1][0] = 0;
  for (i = 1; i <= n; i++) {
    cin >> a;
    nr2 = 0;
    nr5 = 0;
    while (a % 2 == 0) {
      nr2++;
      a /= 2;
    }
    while (a % 5 == 0) {
      nr5++;
      a /= 5;
    }
    aux = nr2 - nr5;
    nr = min(nr2, nr5);
    if (aux > 0) {
      for (l = k; l >= 1; l--) {
        for (j = 0; j <= 12600; j++) {
          if (j < aux) {
            if (d[l - 1][0][aux - j] != -1)
              d[l][1][j] = max(d[l][1][j], d[l - 1][0][aux - j] + nr + aux - j);
          } else if (d[l - 1][1][j - aux] != -1)
            d[l][1][j] = max(d[l][1][j], d[l - 1][1][j - aux] + nr);
        }
        for (j = 1; j <= 12600 - aux; j++)
          if (d[l - 1][0][j + aux] != -1)
            d[l][0][j] = max(d[l][0][j], d[l - 1][0][j + aux] + nr + aux);
      }
    } else {
      aux = -aux;
      for (l = k; l >= 1; l--) {
        for (j = 1; j <= 12600; j++) {
          if (j <= aux) {
            if (d[l - 1][1][aux - j] != -1)
              d[l][0][j] = max(d[l][0][j], d[l - 1][1][aux - j] + nr + aux - j);
          } else if (d[l - 1][0][j - aux] != -1)
            d[l][0][j] = max(d[l][0][j], d[l - 1][0][j - aux] + nr);
        }
        if (d[l - 1][1][aux] != -1)
          d[l][1][0] = max(d[l][1][0], d[l - 1][1][aux] + nr + aux);
        for (j = 1; j <= 12600 - aux; j++)
          if (d[l - 1][1][j + aux] != -1)
            d[l][1][j] = max(d[l][1][j], d[l - 1][1][j + aux] + nr + aux);
      }
    }
  }
  for (j = 0; j <= 12600; j++)
    sol = max(sol, d[k][0][j]), sol = max(sol, d[k][1][j]);
  cout << sol;
  return 0;
}
