#1305. [CQOI2009]dance跳舞

[CQOI2009]dance跳舞

题目描述

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

输入格式

第一行包含两个整数 nnkk
以下 nn 行每行包含 nn 个字符,其中第 ii 行第 jj 个字符为 Y 当且仅当男孩 ii 和女孩 jj 相互喜欢。

输出格式

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

样例输入

3 0
YYY
YYY
YYY

样例输出

3

数据规模与约定

n50,k30n\leq 50,k\leq 30

题目来源

加强数据 By dwellings and liyizhen2