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 maxN = 256;
const int INFINITO = 1e8;
int max2[maxN * 32][maxN][2];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int n, k;
  while (cin >> n >> k) {
    vector<pair<int, int> > f(n, {0, 0});
    for (int i = 0; i < int(n); i++) {
      long long a;
      cin >> a;
      while (a % 2 == 0) {
        f[i].first++;
        a /= 2;
      }
      while (a % 5 == 0) {
        f[i].second++;
        a /= 5;
      }
    }
    for (int r = 0; r < int(maxN * 32); r++)
      for (int i = 0; i < int(maxN); i++)
        for (int p = 0; p < int(2); p++) max2[r][i][p] = -INFINITO;
    max2[f[0].second][1][0] = f[0].first;
    max2[0][0][0] = 0;
    int ans = min(f[0].second, f[0].first);
    for (int i = (1); i < int(n); i++) {
      for (int r = 0; r < int(maxN * 32); r++) {
        for (int j = 0; j < int(k); j++) {
          if (max2[r][j][(i + 1) % 2] != -INFINITO) {
            max2[r][j][i % 2] = max(max2[r][j][i % 2], max2[r][j][(i + 1) % 2]);
            max2[r + f[i].second][j + 1][i % 2] =
                max(max2[r + f[i].second][j + 1][i % 2],
                    max2[r][j][(i + 1) % 2] + f[i].first);
            ans = max(
                ans, min(r + f[i].second, max2[r + f[i].second][j + 1][i % 2]));
          }
        }
      }
    }
    cout << ans << "\n";
  }
  return 0;
}
