[CQOI2009]dance跳舞

一次舞会有 $n$ 个男孩和 $n$ 个女孩。每首曲子开始时，所有男孩和女孩恰好配成 $n$ 对跳交谊舞。每个男孩都不会和同一个女孩跳两首（或更多）舞曲。

有一些男孩女孩相互喜欢，而其他相互不喜欢（不会「单向喜欢」）。每个男孩最多只愿意和 $k$ 个不喜欢的女孩跳舞，而每个女孩也最多只愿意和 $k$ 个不喜欢的男孩跳舞。

给出每对男孩女孩是否相互喜欢的信息，舞会最多能有几首舞曲？

输入格式

第一行包含两个整数 $n$ 和 $k$。

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

输出格式

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

样例输入

3 0
YYY
YYY
YYY

样例输出

3

样例解释

三个男孩与三个女孩两两相互喜欢，因此 $k=0$ 的限制不起作用。每个男孩可以和三个女孩各跳一首，一共能跳 $3$ 首舞曲。

数据范围

• $n\le 50$；
• $k\le 30$。

来源与许可

本题为 CQOI 2009 试题「dance 跳舞」，题面与测试数据整理自 BZOJ 1305。

样例 1

输入

3 0
YYY
YYY
YYY

输出

3