#include<bits/stdc++.h>
#define int long long
#define inf 1e15
using namespace std;
const int maxn=5e5+5;
int n,m;
struct st
{
	int pre,v,w;
}e[maxn<<1];
int g=1,last[maxn],d;
void add(int u,int v,int w)
{
	e[++g].v=v;
	e[g].w=w;
	e[g].pre=last[u];
	last[u]=g;
}
int dis[maxn];
int S,T;
bool bfs()
{
	for(int i=0;i<=1000;i++)dis[i]=0;
	
	queue<int>q;
	q.push(S);
	dis[S]=1;
	while(!q.empty())
	{
		int top=q.front();
		q.pop();
		for(int i=last[top];i;i=e[i].pre)
		if(!dis[e[i].v] && e[i].w)
		{
			dis[e[i].v]=dis[top]+1;
			if(e[i].v==T)
			{
				while(!q.empty())q.pop();
				return 1;
			}
			q.push(e[i].v);
		}
	}
	return 0;
}
int nx[maxn],vis[maxn];
int dfs(int u,int flow)
{
	if(u==T)return flow;
	int sum=0;
	for(int i=last[u];i;i=e[i].pre)
	{
		if(dis[e[i].v]==dis[u]+1 && e[i].w)
		{
			int sav=dfs(e[i].v,min(e[i].w,flow));
			if(sav>0)
			{
				e[i].w-=sav;
				e[i^1].w+=sav;
				sum+=sav;
				flow-=sav;
				if(!flow)return sum;
			}
			else dis[e[i].v]=-1;
		}
	}
	return sum;
}
void add1(int u,int v,int w)
{
	add(u,v,w);
	add(v,u,0);
}
int ans=0,t;
char a[105][105];
int x,last1[maxn],k;
bool check()
{
	ans=0;
	while(bfs())ans+=dfs(S,inf);
	return ans==n;
}
signed main()
{
	cin>>n>>k;
	S=0,T=4*n+1;
	for(int i=1;i<=n;i++)
		scanf("%s",a[i]+1);
	for(int i=1;i<=n;i++)
	{
		add1(i,i+n,k);
		add1(2*n+i,3*n+i,k);
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(a[i][j]=='Y')add1(i,3*n+i,1);
			else add1(n+i,2*n+i,1);
		}
	}
	int p=g+1;
	for(int i=1;i<=n;i++)
	{
		add1(S,i,1);
		add1(3*n+i,T,1);
	}
	int l=0;
	while(check())
	{
		l++;
		for(int i=p;i<=p+4*n;i+=2)
		{
			e[i].w+=e[i^1].w;
			e[i^1].w=0;
		}
	}
	cout<<l;
	return 0;
}