#include<bits/stdc++.h>

using namespace std;

#pragma comment(linker, "/STACK:102400000,102400000")

#define ls i<<1

#define rs ls | 1

#define mid ((ll+rr)>>1)

#define pii pair<int,int>

#define MP make_pair

typedef long long LL;

const long long INF = 1e18+1LL;

const double Pi = acos(-1.0);

const int N = , M = 1e3+, mod = 1e9+, inf = 2e9;

char mp[][];

int n,k,head[N],t=,h[N],q[N],S,T,ans;

struct edge{int to,next,v;}e[N * ];

void adds(int u,int v,int w) {e[t].to=v;e[t].v=w;e[t].next=head[u];head[u]=t++;}

void add(int u,int v,int w) {adds(u,v,w);adds(v,u,);}

int bfs() {

    memset(h,-,sizeof(h));

    int l=,r=,now;

    q[l]=S;

    h[S]=;

    while(l!=r){

        now=q[l++];if(l == ) l=;

        for(int i=head[now];i!=-;i=e[i].next) {

            if(e[i].v&&h[e[i].to]==-) {

                h[e[i].to]=h[now]+;

                q[r++]=e[i].to;

                if(r==) r = ;

            }

        }

    }

    if(h[T]==-) return ;

    else return ;

}

int dfs(int x,int f) {

        if(x == T) return f;

        int used=,w;

        for(int i=head[x]; i!=-;i=e[i].next) {

            if(e[i].v&&h[e[i].to] == h[x] + ) {

                w=dfs(e[i].to,min(f-used,e[i].v));

                used+=w;e[i].v-=w;e[i^].v+=w;

                if(used == f) return f;

            }

        }

        return used;

}

void dinic() {while(bfs()) ans+=dfs(S,inf);}

int check(int x) {

    t = ;S = *n+, T = S+;

    memset(head,-,sizeof(head));

        for(int i=;i<=n;++i) {

            add(S,i,x);

            add(i,i+n,k);

            add(*n+i+n,i+*n,k);

            add(*n+i,T,x);

        }

        for(int i=;i<=n;++i) {

            for(int j=;j<=n;++j) {

                if(mp[i][j] == 'Y') {

                    add(i,*n+j,);

                }

                else add(i+n,*n+n+j,);

            }

        }ans = ;

        dinic();

        if(ans == n*x) return ;

        else return ;

}

int main() {

        scanf("%d%d",&n,&k);

        for(int i=;i<=n;++i) scanf("%s",mp[i]+);

        int l = , r = n,ans1;

        while(l <= r) {

            int md = (l+r)>>;

            if(check(md)) {

                ans1 = md;l = md+;

            } else r = md-;

        }

        printf("%d\n",ans1);

        return ;

}