一次舞会有n个男孩和n个女孩。每首曲子开始时，所有男孩和女孩恰好配成n对跳交谊舞。每个男孩都不会和同一个女孩跳两首（或更多）舞曲。
有一些男孩女孩相互喜欢，而其他相互不喜欢（不会“单向喜欢”）。每个男孩最多只愿意和k个不喜欢的女孩跳舞，而每个女孩也最多只愿意和k个不喜欢的男孩跳舞。
给出每对男孩女孩是否相互喜欢的信息，舞会最多能有几首舞曲？

Input

第一行包含两个整数n和k。以下n行每行包含n个字符，其中第i行第j个字符为'Y'当且仅当男孩i和女孩j相互喜欢。

Output

仅一个数，即舞曲数目的最大值。

Sample Input

YYY

YYY

YYY

Sample Output

Hint

N<= K<=

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

const int inf=;

const int maxn=;

char mp[][];

int Laxt[maxn],Next[maxn],To[maxn],cap[maxn],cnt;

int dis[maxn],vd[maxn],S,N,T,K;

void add(int u,int v,int val)

{

    Next[++cnt]=Laxt[u];

    Laxt[u]=cnt;

    To[cnt]=v;

    cap[cnt]=val;

}

int sap(int u,int flow)

{

    if(flow==||u==T) return flow;

    int tmp,delta=;

    for(int i=Laxt[u];i;i=Next[i]){

        if(dis[u]==dis[To[i]]+&&cap[i]>){

           tmp=sap(To[i],min(cap[i],flow-delta));

            delta+=tmp;

           cap[i]-=tmp;

           cap[i^]+=tmp;

           if(delta==flow||dis[S]>T+) return delta;

        }

    }

    vd[dis[u]]--;

    if(vd[dis[u]]==) dis[S]=T+;

    vd[++dis[u]]++;

    return delta;

}

bool check(int num)

{

    int res=; cnt=;

    for(int i=S;i<=T;i++) Laxt[i]=dis[i]=vd[i]=;

    for(int i=;i<=N;i++) { add(S,i,num); add(i,S,); } //分散给男生

    for(int i=;i<=N;i++) { add(i,N+i,K); add(N+i,i,); } //给不喜欢的分配名额

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

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

       if(mp[i][j]=='Y'){ add(i,*N+j,);add(*N+j,i,); } //给喜欢的女生分配

       else { add(N+i,*N+j,); add(*N+j,N+i,);  }//给不喜欢的分配

    for(int i=*N+;i<=*N+N;i++){ add(i,N+i,K); add(T,i,); } //汇聚到女生

    for(int i=*N+;i<=*N+N;i++){ add(i,T,num); add(T,i,); } //汇聚到汇点

    while(dis[S]<=T+) res+=sap(S,inf);

    if(res==num*N) return true;

    return false;

}

int main()

{

    scanf("%d%d",&N,&K); S=; T=*N+;

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

    int L=,R=N,Mid,ans=;

    while(L<=R){

        Mid=(L+R)>>;

        if(check(Mid)) ans=Mid,L=Mid+;

        else R=Mid-;

    }

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

    return ;

}