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;
string i_s(int x) {
  if (x == 0) return "0";
  string ret = "";
  while (x) {
    ret = ret + (char)(x % 10 + '0');
    x /= 10;
  }
  reverse(ret.begin(), ret.end());
  return ret;
}
string add(string a, string b) {
  if (a == "") a = "0";
  if (b == "") b = "0";
  if (a.length() < b.length()) swap(a, b);
  while (b.length() < a.length()) {
    b = '0' + b;
  }
  for (int i = 0; i < a.length(); i++) {
    a[i] = a[i] + (b[i] - '0');
  }
  bool big = false;
  for (int i = a.length() - 1; i >= 0; i--) {
    if (big) {
      a[i]++;
    }
    big = false;
    if (a[i] > '9') {
      a[i] = a[i] - 10;
      big = true;
    }
  }
  if (big) a = '1' + a;
  return a;
}
string mul(string a, string b) {
  vector<int> va, vb;
  if (a == "0" || b == "0") return "0";
  string ans;
  for (int i = 0; i < a.length(); i++) {
    va.push_back(a[i] - '0');
  }
  for (int i = 0; i < b.length(); i++) {
    vb.push_back(b[i] - '0');
  }
  reverse(va.begin(), va.end());
  reverse(vb.begin(), vb.end());
  vector<int> res;
  res.clear();
  res.resize(1005);
  for (int i = 0; i < a.length(); i++) {
    for (int j = 0; j < b.length(); j++) {
      res[i + j] += (va[i] * vb[j]);
    }
  }
  for (int i = 0; i < 1005; i++) {
    if (res[i] > 9) {
      res[i + 1] += (res[i] / 10);
      res[i] %= 10;
    }
  }
  for (int i = 0; i < 1005; i++) {
    ans += (res[i] + '0');
  }
  reverse(ans.begin(), ans.end());
  int k = 0;
  while (ans[k] == '0') {
    k++;
  }
  ans = ans.substr(k);
  return ans;
}
bool is_prime(int n) {
  if (n < 2) return false;
  for (int i = 2; i * i <= n; i++)
    if (n % i == 0) return false;
  return true;
}
long long n, k, num2[205], num5[205], dp[2][205][10005], ans;
int main() {
  cin >> n >> k;
  for (long long i = 1; i <= n; i++) {
    long long x;
    cin >> x;
    while (x % 2 == 0) {
      x /= 2;
      num2[i]++;
    }
    while (x % 5 == 0) {
      x /= 5;
      num5[i]++;
    }
  }
  memset(dp, -127, sizeof(dp));
  dp[0][0][0] = 0;
  for (long long i = 1; i <= n; i++) {
    memset(dp[i & 1], -127, sizeof(dp[i & 1]));
    for (long long j = 0; j <= k; j++) {
      for (long long z = 0; z <= j * 50; z++) {
        if (z >= num5[i])
          dp[i & 1][j][z] = max(dp[(i - 1) & 1][j][z],
                                dp[(i - 1) & 1][j - 1][z - num5[i]] + num2[i]);
        else
          dp[i & 1][j][z] = dp[(i - 1) & 1][j][z];
      }
    }
  }
  for (long long i = 0; i <= n * 50; i++)
    ans = max(ans, min(i, dp[n & 1][k][i]));
  cout << ans;
  return 0;
}
