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>
int Tss[210], Fss[210], Exs[210];
long long Arr[210];
int N, K;
int DPF[210][5300 * 2 + 10], DPB[210][5300 * 2 + 10];
int Max;
void DPA() {
  int wi;
  int wic, win;
  int cs, ex;
  memset(DPF, -0x3F, sizeof(DPF));
  memset(DPB, -0x3F, sizeof(DPB));
  DPF[0][5300] = DPB[0][5300] = 0;
  for (wi = 1; wi <= N; ++wi) {
    for (wic = 0; wic <= (K > wi ? wi : K); ++wic)
      for (win = 0; win <= 5300 * 2; ++win)
        if (DPF[wic][win] >= 0) {
          cs = win - 5300;
          ex = Exs[wi];
          if (cs < 0)
            ex += (Fss[wi] > -cs ? -cs : Fss[wi]);
          else
            ex += (cs > Tss[wi] ? Tss[wi] : cs);
          cs -= Tss[wi] - Fss[wi];
          cs += 5300;
          if (cs < 0) cs = 0;
          if (cs > 5300 * 2) cs = 5300 * 2;
          if (ex + DPF[wic][win] > DPB[wic + 1][cs])
            DPB[wic + 1][cs] = ex + DPF[wic][win];
        }
    for (win = 0; win <= 5300 * 2; ++win)
      Max = ((Max) > (DPB[K][win]) ? (Max) : (DPB[K][win]));
    memcpy(DPF, DPB, sizeof(DPF));
  }
}
int main() {
  scanf("%d %d", &N, &K);
  int wi;
  for (wi = 1; wi <= N; ++wi) std::cin >> Arr[wi];
  for (wi = 1; wi <= N; ++wi) {
    while ((Arr[wi] % 2) == 0) {
      ++Tss[wi];
      Arr[wi] /= 2;
    }
    while ((Arr[wi] % 5) == 0) {
      ++Fss[wi];
      Arr[wi] /= 5;
    }
    Exs[wi] = (Fss[wi] > Tss[wi] ? Tss[wi] : Fss[wi]);
    Tss[wi] -= Exs[wi];
    Fss[wi] -= Exs[wi];
  }
  DPA();
  printf("%d\n", Max);
}
