#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using PII = pair<int, int>;
using PLL = pair<ll, ll>;
const int N = 110 + 10;
const int M = 131;
const int INF = 0x3f3f3f3f;
const ll LNF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const int V = 2e3 + 10;
const int E = 2e5 + 10;
template<typename T>
struct FlowGraph {
	int s, t, vtot;
	int head[V], etot;
	int dis[V], cur[V];
	struct edge {
		int v, nxt;
		T f;
	} e[E * 2];
	void add(int u, int v, T f) {
		e[etot] = {v, head[u], f}; head[u] = etot++;
		e[etot] = {u, head[v], 0}; head[v] = etot++;
	}
	bool bfs() {
		for (int i = 1; i <= vtot; i++) {
			dis[i] = 0;
			cur[i] = head[i];
		}
		queue<int> q;
		q.push(s); dis[s] = 1;
		while (!q.empty()) {
			int u = q.front(); q.pop();
			for (int i = head[u]; ~i; i = e[i].nxt) {
				if (e[i].f && !dis[e[i].v]) {
					int v = e[i].v;
					dis[v] = dis[u] + 1;
					if (v == t) return true;
					q.push(v);
				}
			}
		}
		return false;
	}
	T dfs(int u, T m) {
		if (u == t) return m;
		T flow = 0;
		for (int i = cur[u]; ~i; cur[u] = i = e[i].nxt)
			if (e[i].f && dis[e[i].v] == dis[u] + 1) {
			T f = dfs(e[i].v, min(m, e[i].f));
			e[i].f -= f;
			e[i ^ 1].f += f;
			m -= f;
			flow += f;
			if (!m) break;
		}
		if (!flow) dis[u] = -1;
		return flow;
	}
	T dinic() {
		T flow = 0;
		while (bfs()) flow += dfs(s, numeric_limits<T>::max());
		return flow;
	}
	void init(int s_, int t_, int vtot_) {
		s = s_;
		t = t_;
		vtot = vtot_;
		etot = 0;
		for (int i = 1; i <= vtot; i++) head[i] = -1;
	}
	T check_min_path(){
		for(int i = 0; i < etot; i += 2){
			if(e[i].f == 0) e[i].f = 1;
			else e[i].f = INF;
			e[i ^ 1].f = 0;
		}
		return dinic();
	}
};
FlowGraph<ll> g;

void solve(){
	int n, m; cin >> n >> m;
	vector<vector<int>> ve(n + 1, vector<int> (n + 1)); 
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			char p; cin >> p;
			ve[i][j] = (p == 'Y') ? 1 : 0;
		}
	}
	int l = 0, r = n;
	while(l < r){
		int mid = (l + r + 1) >> 1;
		int s = 5 * n + 1, t = 5 * n + 2;
		g.init(s, t, 5 * n + 2);
		for(int i = 1; i <= n; i++) g.add(s, i, INF);
		for(int i = 1; i <= n; i++) g.add(3 * n + i, t, INF);
		
		for(int i = 1; i <= n; i++) g.add(i, i + n, mid);
		for(int i = 1; i <= n; i++) g.add(i + 2 * n, i + 3 * n, mid);
		
		for(int i = 1; i <= n; i++) g.add(i + n, i + 4 * n, m);
		
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++){
				if(ve[i][j] == 1){
					g.add(i + n, j + 2 * n, 1);
				}
				else g.add(i + 4 * n, j + 3 * n, 1);
			}
		}
		int num = g.dinic();
		if(num == n * mid) l = mid;
		else r = mid - 1;
	}
	cout << l << endl;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout << fixed << setprecision(12);
	int t = 1;
	//cin >> t;
	while(t--){
		solve();
	}
	return 0 - 0;
}