#include<algorithm>

#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iomanip>

#include<iostream>

#include<map>

#include<queue>

#include<stack>

#include<vector>

#define rep(i,x,y) for(register int i=(x);i<=(y);++i)

#define dwn(i,x,y) for(register int i=(x);i>=(y);--i)

#define re register

#define maxn 510

#define maxm 500010

using namespace std;

inline int read()

{

    int x=0,f=1;

    char ch=getchar();

    while(isdigit(ch)==0 && ch!='-')ch=getchar();

    if(ch=='-')f=-1,ch=getchar();

    while(isdigit(ch))x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

    return x*f;

}

inline void write(int x)

{

    int f=0;char ch[20];

    if(!x){puts("0");return;}

    if(x<0){putchar('-');x=-x;}

    while(x)ch[++f]=x%10+'0',x/=10;

    while(f)putchar(ch[f--]);

    putchar('\n');

}

int n,K,fir[maxn],nxt[maxm],v[maxm],fl[maxm],dis[maxn],maxflow,cnt,l,r,ans,s,t,inf[3];

char yes[60][60];

queue<int >q;

void ade(int u1,int v1,int fl1)

{

	v[cnt]=v1,fl[cnt]=fl1,nxt[cnt]=fir[u1],fir[u1]=cnt++;

	v[cnt]=u1,fl[cnt]=0,nxt[cnt]=fir[v1],fir[v1]=cnt++;

}

void reset(){memset(fir,-1,sizeof(fir)),maxflow=cnt=0;}

int bfs()

{

	memset(dis,-1,sizeof(dis));

	dis[t]=0;q.push(t);

	while(!q.empty())

	{

		int u=q.front();q.pop();

		for(int k=fir[u];k!=-1;k=nxt[k])

		{

			int vv=v[k];

			if(fl[k^1]&&dis[vv]==-1)

			{

				dis[vv]=dis[u]+1;

				q.push(vv);

			}

		}

	}

	return dis[s]==-1?0:1;

}

int dfs(int u,int nowflow)

{

	if(u==t||!nowflow)return nowflow;

	int tmp,sum=0;

	for(int k=fir[u];k!=-1;k=nxt[k])

	{

		if(!nowflow)break;

		int vv=v[k];

		if(dis[vv]+1==dis[u]&&fl[k]&&(tmp=dfs(vv,min(fl[k],nowflow)))>0)

			fl[k]-=tmp,fl[k^1]+=tmp,nowflow-=tmp,sum+=tmp;

	}

	return sum;

}

int check(int tim)

{

	s=0,t=n*4+1;

	rep(i,1,n)ade(s,i,tim),ade(i,i+n,K),ade(i+n*2,t,tim),ade(i+n*3,i+n*2,K);

	rep(i,1,n)

	    rep(j,1,n)

	    {

	    	if(yes[i][j]=='Y')ade(i,j+n*2,1);

	    	else ade(i+n,j+n*3,1);

	    }

	while(bfs())maxflow+=dfs(s,inf[0]);

	return (maxflow==n*tim);

}

int main()

{

    memset(inf,0x7f,sizeof(inf));

    n=read(),K=read();

    rep(i,1,n){scanf("%s",yes[i]+1);}

    l=0,r=n;

    while(l<=r)

    {

    	reset();

    	int mid=(l+r)>>1;

    	if(check(mid))ans=mid,l=mid+1;

    	else r=mid-1;

    }

    write(ans);

	return 0;

}