P2015 - 【最大流】[CQOI2009]跳舞

Problem

P2015【最大流】[CQOI2009]跳舞

Limits : Time Limit : 10000 MS Memory Limit : 65536 KB

Description

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

Input Format

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

Output Format

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

Sample Input

样例输入1：
3 0
YYY
YYY
YYY

样例输入2：
3 0
YYY
YYN
YNY

样例输入3：
2 0
YN
YN

样例输入4：
2 1
YN
YN

Sample Output

样例输出1：
3

样例输出2：
2

样例输出3：
0

样例输出4:
1

Hint


【数据规模】
数据	1	2	3	4	5	6	7	8	9	10
n	1	3	5	8	10	40	40	50	50	50
k	1	2	2	1	4	0	14	10	20	30