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.

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 a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10¹⁸).

Print maximal roundness of product of the chosen subset of length k.

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.

  1 /**  2  * Codeforces  3  * Problem#837D  4  * Accepted  5  * Time: 187ms  6  * Memory: 10604k  7  */  8 #include <bits/stdc++.h>  9 using namespace std; 10 typedef bool boolean; 11 #define smax(a, b) a = max(a, b); 12 template<typename T> 13 inline boolean readInteger(T& u){ 14     char x; 15     int aFlag = 1; 16     while(!isdigit((x = getchar())) && x != ‘-‘ && x != -1); 17     if(x == -1) { 18         ungetc(x, stdin);     19         return false; 20     } 21     if(x == ‘-‘){ 22         x = getchar(); 23         aFlag = -1; 24     } 25     for(u = x - ‘0‘; isdigit((x = getchar())); u = (u << 1) + (u << 3) + x - ‘0‘); 26     ungetc(x, stdin); 27     u *= aFlag; 28     return true; 29 } 30  31 typedef class Status { 32     public: 33         int stage; 34         int seced; 35         int c5; 36 }Status; 37  38 int n, k; 39 int *c2s, *c5s; 40 int res = 0; 41  42 inline void init() { 43     long long x; 44     readInteger(n); 45     readInteger(k); 46     c2s = new int[(n + 1)]; 47     c5s = new int[(n + 1)]; 48     for(int i = 1; i <= n; i++) { 49         c2s[i] = c5s[i] = 0; 50         readInteger(x); 51         while(!(x & 1))    x >>= 1, c2s[i]++; 52         while(!(x % 5))    x /= 5, c5s[i]++; 53     } 54 } 55  56 queue<Status> que; 57 int f[2][201][4001]; 58 inline void dp() { 59     int last = 0; 60     Status sta = (Status) {0, 0, 0}; 61     que.push(sta); 62     memset(f, -1, sizeof(f)); 63     f[0][0][0] = 0; 64     while(!que.empty()) { 65         Status e = que.front(); 66         que.pop(); 67          68         int lastf = f[e.stage & 1][e.seced][e.c5]; 69         Status eu = e; 70         eu.stage++; 71         if(eu.stage != last) { 72             last = eu.stage; 73             memset(f[eu.stage & 1], -1, sizeof(f[0])); 74         } 75          76         if(f[eu.stage & 1][eu.seced][eu.c5] == -1 && eu.stage < n && eu.seced <= k) 77             que.push(eu); 78         else if(eu.stage == n && eu.seced == k) 79             smax(res, min(eu.c5, lastf)); 80         smax(f[eu.stage & 1][eu.seced][eu.c5], lastf); 81          82         eu.seced++, eu.c5 += c5s[eu.stage]; 83         if(f[eu.stage & 1][eu.seced][eu.c5] == -1 && eu.stage < n && eu.seced <= k) 84             que.push(eu); 85         else if(eu.stage == n && eu.seced == k) 86             smax(res, min(eu.c5, lastf + c2s[eu.stage])); 87         smax(f[eu.stage & 1][eu.seced][eu.c5], lastf + c2s[eu.stage]); 88     } 89 } 90  91 inline void solve() { 92     printf("%d\n", res); 93 } 94  95 int main() { 96     init(); 97     dp(); 98     solve(); 99     return 0;100 }