1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 205

 4 struct ji{

 5     int nex,to,len;

 6 }edge[N*N];

 7 queue<int>q;

 8 int E,n,k,head[N],work[N],d[N];

 9 char s[N][N];

10 void add(int x,int y,int z){

11     edge[E].nex=head[x];

12     edge[E].to=y;

13     edge[E].len=z;

14     head[x]=E++;

15     if (E&1)add(y,x,0);

16 }

17 bool bfs(){

18     memset(d,-1,sizeof(d));

19     q.push(0);

20     d[0]=0;

21     while (!q.empty()){

22         int k=q.front();

23         q.pop();

24         for(int i=head[k];i!=-1;i=edge[i].nex)

25             if ((edge[i].len)&&(d[edge[i].to]<0)){

26                 d[edge[i].to]=d[k]+1;

27                 q.push(edge[i].to);

28             }

29     }

30     return d[4*n+1]>=0;

31 }

32 int dfs(int k,int s){

33     if (k>4*n)return s;

34     for(int &i=work[k];i!=-1;i=edge[i].nex)

35         if ((edge[i].len)&&(d[edge[i].to]==d[k]+1)){

36             int p=dfs(edge[i].to,min(s,edge[i].len));

37             if (p){

38                 edge[i].len-=p;

39                 edge[i^1].len+=p;

40                 return p;

41             }

42         }

43     return 0;

44 }

45 int dinic(){

46     int k,ans=0;

47     while (bfs()){

48         memcpy(work,head,sizeof(head));

49         while (k=dfs(0,0x3f3f3f3f))ans+=k;

50     }

51     return ans;

52 }

53 bool pd(int mid){

54     memset(head,-1,sizeof(head));

55     E=0;

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

57         add(0,i,mid);

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

59         add(i+2*n,4*n+1,mid);

60         add(i+3*n,i+2*n,k);

61     }

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

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

64             if (s[i][j]=='Y')add(i,j+2*n+1,1);

65             else add(i+n,j+3*n+1,1);

66     return dinic()==mid*n;

67 }

68 int main(){

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

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

71     int l=0,r=n;

72     while (l<r){

73         int mid=(l+r+1>>1);

74         if (pd(mid))l=mid;

75         else r=mid-1;

76     }

77     printf("%d",l);

78 }