#include<bits/stdc++.h>

 #define IOS ios::sync_with_stdio(false);//不可再使用scanf printf

 #define Max(a, b) ((a) > (b) ? (a) : (b))//禁用于函数，会超时

 #define Min(a, b) ((a) < (b) ? (a) : (b))

 #define Mem(a) memset(a, 0, sizeof(a))

 #define Dis(x, y, x1, y1) ((x - x1) * (x - x1) + (y - y1) * (y - y1))

 #define MID(l, r) ((l) + ((r) - (l)) / 2)

 #define lson ((o)<<1)

 #define rson ((o)<<1|1)

 #define Accepted 0

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

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}

     while (ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 typedef long long ll;

 const int maxn =  + ;

 const int MOD = ;//const引用更快，宏定义也更快

 const int INF = 1e9 + ;

 const double eps = 1e-;

 struct edge

 {

     int u, v, c, f;

     edge(int u, int v, int c, int f):u(u), v(v), c(c), f(f){}

 };

 vector<edge>e;

 vector<int>G[maxn];

 int level[maxn];//BFS分层，表示每个点的层数

 int iter[maxn];//当前弧优化

 void init(int n)

 {

     for(int i = ; i <= n; i++)G[i].clear();

     e.clear();

 }

 void addedge(int u, int v, int c)

 {

     e.push_back(edge(u, v, c, ));

     e.push_back(edge(v, u, , ));

     int m = e.size();

     G[u].push_back(m - );

     G[v].push_back(m - );

 }

 void BFS(int s)//预处理出level数组

 //直接BFS到每个点

 {

     memset(level, -, sizeof(level));

     queue<int>q;

     level[s] = ;

     q.push(s);

     while(!q.empty())

     {

         int u = q.front();

         q.pop();

         for(int v = ; v < G[u].size(); v++)

         {

             edge& now = e[G[u][v]];

             if(now.c > now.f && level[now.v] < )

             {

                 level[now.v] = level[u] + ;

                 q.push(now.v);

             }

         }

     }

 }

 int dfs(int u, int t, int f)//DFS寻找增广路

 {

     if(u == t)return f;//已经到达源点，返回流量f

     for(int &v = iter[u]; v < G[u].size(); v++)

         //这里用iter数组表示每个点目前的弧，这是为了防止在一次寻找增广路的时候，对一些边多次遍历

         //在每次找增广路的时候，数组要清空

     {

         edge &now = e[G[u][v]];

         if(now.c - now.f >  && level[u] < level[now.v])

             //now.c - now.f > 0表示这条路还未满

             //level[u] < level[now.v]表示这条路是最短路，一定到达下一层，这就是Dinic算法的思想

         {

             int d = dfs(now.v, t, min(f, now.c - now.f));

             if(d > )

             {

                 now.f += d;//正向边流量加d

                 e[G[u][v] ^ ].f -= d;

     //反向边减d，此处在存储边的时候两条反向边可以通过^操作直接找到

                 return d;

             }

         }

     }

     return ;

 }

 int Maxflow(int s, int t)

 {

     int flow = ;

     for(;;)

     {

         BFS(s);

         if(level[t] < )return flow;//残余网络中到达不了t，增广路不存在

         memset(iter, , sizeof(iter));//清空当前弧数组

         int f;//记录增广路的可增加的流量

         while((f = dfs(s, t, INF)) > )

         {

             flow += f;

         }

     }

     return flow;

 }

 int n, k;

 char Map[][];

 bool judge(int m)

 {

     int s = , t =  * n + ;

     init(t);

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

     {

         addedge(s, i, m);

         addedge(i, n + i, INF);

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

         addedge( * n + i,  * n + i, INF);

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

         addedge( * n + i, t, m);

     }

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

     {

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

         {

             if(Map[i][j] == 'Y')//互相喜欢

                 addedge(n + i,  * n + j, );

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

         }

     }

     return Maxflow(s, t) == n * m;

 }

 int main()

 {

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

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

     int l = , r = n;

     int ans = ;

     while(l <= r)

     {

         int m = (l + r) / ;

         if(judge(m))ans = m, l = m + ;

         else r = m - ;

     }

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

     return Accepted;

 }