Танцы на вечеринке
Танцы на вечеринке
На вечеринку приглашены n мальчиков и nдевочек. Они хотят станцевать несколько раундов.
В каждом раунде гости делятся на n танцующих пар. Каждый гость должен быть в некоторой паре, каждая пара должна состоять из одного мальчика и одной девочки. В каждом раунде каждый мальчик должен танцевать с другой девочкой. Некоторые мальчики и девочки не нравятся друг другу. Каждый мальчик может танцевать не более чем с k девочками, которые ему не нравятся. Аналогично каждая девочка может танцевать не более чем с k мальчиками, которые ей не нравятся.
Имеется информация о том, нравятся ли друг другу i-ый мальчик и j-ая девочка (1 ≤ i, j ≤ n). Найти наибольшее количество раундов, которое можно станцевать на вечеринке.
Входные данные
Первая строка содержит два числа: n и k (1 ≤ n ≤ 50, 0 ≤ k ≤ 50). j-ый символ в i-ой строке матрицы содержит 'Y', если i-ый мальчик и j-ая девочка нравятся друг другу, и 'N' в противном случае.
Выходные данные
Вывести наибольшее количество раундов, которое можно станцевать на вечеринке.
Пример
3 0 YYY YYN YNY
2
2 1 YN YN
1