Description

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?

Input Format

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 Format

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

3 0
YYY
YYY
YYY

3

Hint

Constraints

• For $100\%$ of the testdata, it is guaranteed that $1 \le n \le 50$, $0 \le k \le 30$.

Translated by ChatGPT 5