#include<cstdio>

#include<cstring>

using namespace std;

const int inf=0x3f3f3f3f;

int n,k,mid,ans;

int d[250];

int q[250],h,t;

int start=1,end;

int head[250],cnt=2;

char ch[60];

struct Edge{

	int to,nxt,cost;

}e[1000000];

int v[60][60];

inline int min(int a,int b){return a<b?a:b;}

void add(int a,int b,int c){

	e[cnt]=(Edge){b,head[a],c};head[a]=cnt;

	e[cnt^1]=(Edge){a,head[b],0};head[b]=cnt^1;

	cnt+=2;

}

bool bfs(){

	memset(d,0,sizeof d);

	d[q[t=h=1]=start]=1;

	while (h<=t){

		int x=q[h++];

		if (x==end)return true;

		for (int i=head[x];i;i=e[i].nxt){

			int to=e[i].to;

			if (e[i].cost&&!d[to]){

				d[to]=d[x]+1;

				q[++t]=to;

			}

		}

	}

	return d[end];

}

int dfs(int x,int low){

	if (x==end||!low)return low;

	int res=0,w;

	for (int i=head[x];i;i=e[i].nxt){

		int to=e[i].to;

		if (e[i].cost&&(d[x]==d[to]-1)){

			w=dfs(to,min(e[i].cost,low-res));

			e[i].cost-=w;

			e[i^1].cost+=w;

			res+=w;

			if (res==low)return low;

		}

	}

	if (!res)d[x]=-1;

	return res;

}

void build(int mid){

	memset(head,0,sizeof head);

	cnt=2;

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

		add(start,i+1,mid);

		add(i+n+n+1,end,mid);

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

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

	}

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

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

			if(v[i][j])add(i+1,j+n+n+1,1);

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

}

bool check(int mid){

	build(mid);

//	puts("la");

	int ans=0,k;

	while (bfs()){

		k=dfs(start,inf);

		if (k>0)ans+=k;

	}

	if (ans==mid*n)return true;

	return false;

}

int main(){

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

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

		scanf("%s",ch);

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

			v[i][j]=(ch[j-1]=='Y');

		}

	}

	end=(n<<2)+2;

//	puts("lalal");

	int l=0,r=n;

	while (l<=r){

		mid=l+r>>1;

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

			else r=mid-1;

//		printf("%d\n",mid);

	}

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

	return 0;

}