[CQOI2009]跳舞

题目描述

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

输入输出格式

输入格式


第一行包含两个整数 $n$ 和 $k$。 以下 $n$ 行每行包含 $n$ 个字符,每个字符只可能是 `Y` 或 `N`。第 $(i + 1)$ 行的第 $j$ 个字符为 `Y` 当且仅当男孩 $i$ 和女孩 $j$ 相互喜欢。

输出格式


一行一个整数代表舞曲数目的最大值。

输入输出样例

输入样例 #1

3 0
YYY
YYY
YYY

输出样例 #1

3

说明

#### 数据规模与约定 - 对于 $100\%$ 的数据,保证 $1\leq n\leq 50$,$1\leq k\leq 30$。