P3153 [CQOI2009] Dancing

There are $n$ boys and $n$ girls at a party. At the start of each song, all boys and girls are paired into exactly $n$ couples to dance ballroom. No boy ever dances two (or more) songs with the same girl. Some boy–girl pairs mutually like each other, while others mutually do not; there are no "one-way likes." Each boy is willing to dance with at most $k$ girls he does not like, and each girl is willing to dance with at most $k$ boys she does not like. Given the mutual-like information for every boy–girl pair, what is the maximum number of songs the party can have?

The first line contains two integers $n$ and $k$. Each of the next $n$ lines contains $n$ characters, and each character is either `Y` or `N`. The $j$-th character on line $(i + 1)$ is `Y` if and only if boy $i$ and girl $j$ mutually like each other.

Output a single integer on one line, representing the maximum number of songs.

Constraints - For $100\%$ of the testdata, it is guaranteed that $1 \le n \le 50$, $0 \le k \le 30$. Translated by ChatGPT 5