//  _        ________    ________
// | |      |___  ___|  |  ____  |
// | |         |  |     | |    | |
// | |____     |  |     | |____| \
// |______|    |__|     |_________>
// BY SHADOW_LTQ

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define db double

const int N = 1e4 + 10, M = 1e5 + 10;
int n, k, s, t, kk, dis[N], now[N];
int idx = 1, h[N], w[M], to[M], ne[M];
ll ans;
bool has[N];

void add (int x, int y, int c)
{
	to[++idx] = y;
	ne[idx] = h[x];
	w[idx] = c;
	h[x] = idx;
	to[++idx] = x;
	ne[idx] = h[y];
	w[idx] = 0;
	h[y] = idx;
}

bool bfs ()
{
	memset (dis, 0, sizeof (dis));
	queue <int> q;
	q.push (s);
	dis[s] = 1;
	now[s] = h[s];
	while (q.size ())
	{
		int x = q.front ();
		q.pop ();
		for (int i = h[x]; i; i = ne[i])
		{
			if (w[i] && !dis[to[i]])
			{
				int y = to[i];
				q.push (y);
				now[y] = h[y];
				dis[y] = dis[x] + 1;
				if (y == t)
				{
					return true;
				}
			}
		}
	}
	return false;
}

int dinic (int x, int flow)
{
	if (x == t)
	{
		return flow;
	}
	int rest = flow, k;
	for (int i = now[x]; i && rest; i = ne[i])
	{
		now[x] = i;
		if (w[i] && dis[to[i]] == dis[x] + 1)
		{
			k = dinic (to[i], min (rest, w[i]));
			if (!k)
			{
				dis[to[i]] = 0;
			}
			w[i] -= k;
			w[i ^ 1] += k;
			rest -= k;
		}
	}
	return flow - rest;
}

void build (ll mid)
{
    for (int i = 1; i <= n * n; i++)
    {
        int cv = 1 + i * 2;
        w[cv - 1] = 1;
        w[cv] = 0;
    }
    for (int i = 1; i <= 2 * n; i++)
    {
        int cv = 1 + n * n * 2 + i * 2;
        w[cv - 1] = mid;
        w[cv] = 0;
    }
    for (int i = 1; i <= 2 * n; i++)
    {
        int cv = 1 + n * n * 2 + 4 * n + i * 2;
        w[cv - 1] = k;
        w[cv] = 0;
    }
    for (int i = 1; i <= 2 * n; i++)
    {
        int cv = 1 + n * n * 2 + 8 * n + i * 2;
        w[cv - 1] = INT_MAX;
        w[cv] = 0;
    }
}

int main()
{
	scanf ("%d%d", &n, &k);
    s = 1;
    t = 2 + n * 6;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            char c;
            cin >> c;
            if (c == 'Y')
            {
                add (1 + i, 1 + n + j, 1);
            }
            else
            {
                add (1 + n * 2 + i, i + n * 3 + j, 1);
            }
        }
    }
    for (int i = 1; i <= n; i++)
    {
        add (s, 1 + n * 4 + i, 1);
        add (1 + n * 5 + i, t, 1);
    }
    for (int i = 1; i <= n; i++)
    {
        add (1 + n * 4 + i, 1 + n * 2 + i, k);
        add (1 + n * 3 + i, 1 + n * 5 + i, k);
    }
    for (int i = 1; i <= n; i++)
    {
        add (1 + n * 4 + i, 1 + i, INT_MAX);
        add (1 + n + i, 1 + n * 5 + i, INT_MAX);
    }
	int flow = 0;
    ll l = 0, r = n;
    while (l <= r)
    {
        int res = 0;
        ll mid = (l + r) >> 1;
        build (mid);
        while (bfs ())
        {
            while (flow = dinic (s, INT_MAX))
            {
                res += flow;
            }
        }
        if (res == n * mid)
        {
            l = mid + 1;
            ans = mid;
        }
        else
        {
            r = mid - 1;
        }
    }
    // build (r);
    // int res = 0;
    // while (bfs ())
    // {
    //     while (flow = dinic (s, INT_MAX))
    //     {
    //         res += flow;
    //     }
    // }
    // printf ("%lld", res == n * r ? r : l);
    printf ("%lld", ans);
	return 0;
}