eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Танцы на вечеринке

Танцы на вечеринке

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

На вечеринку приглашены n мальчиков и nдевочек. Они хотят станцевать несколько раундов.

В каждом раунде гости делятся на n танцующих пар. Каждый гость должен быть в некоторой паре, каждая пара должна состоять из одного мальчика и одной девочки. В каждом раунде каждый мальчик должен танцевать с другой девочкой. Некоторые мальчики и девочки не нравятся друг другу. Каждый мальчик может танцевать не более чем с k девочками, которые ему не нравятся. Аналогично каждая девочка может танцевать не более чем с k мальчиками, которые ей не нравятся.

Имеется информация о том, нравятся ли друг другу i-ый мальчик и j-ая девочка (1i, jn). Найти наибольшее количество раундов, которое можно станцевать на вечеринке.

Входные данные

Первая строка содержит два числа: n и k (1n50, 0k50). j-ый символ в i-ой строке матрицы содержит 'Y', если i-ый мальчик и j-ая девочка нравятся друг другу, и 'N' в противном случае.

Выходные данные

Вывести наибольшее количество раундов, которое можно станцевать на вечеринке.

Пример

Входные данные #1
3 0
YYY
YYN
YNY
Выходные данные #1
2
Входные данные #2
2 1
YN
YN
Выходные данные #2
1
Источник Летняя Школа 2010, Севастополь, день М.Медведева