Разрез
Когда Фродо, Сэм, Мерри и Пиппин сидели в Зеленом Драконе и пили пиво, они решили сыграть в небольшую игру с бумагой и ручкой, чтобы решить кто покупает пиво в следующем раунде. Игра имеет следующий вд:
Имеется прямоугольная доска m × n, каждая клетка которой обозначена одной из букв W, I или N. Найдите наибольшее количество триомино, которое можно вырезать из доски таким образом, чтобы клетки W и N были на концах триомино, а I посередине (то есть можно было бы прочитать WIN в некотором порядке). Допустимыми триомино являются последовательности из трех клеток, расположенные в линию или уголком. Тот кто найдет наибольшее количество триомино, выигрывает и указывает на того кто идет за пивом. Вам следует найти наибольшее количество таких слов.
Входные данные
Состоит из нескольких тестов. Каждый тест содержит прямоугольную сетку m × n (1 ≤ m, n ≤ 30), содержащую буквы W, I и N. Тесты отделяются друг от друга пустой строкой.
Выходные данные
Для каждого теста вывести в отдельной строке наибольшее количество триомино, которое можно вырезать из доски.