Розріз#6984
Коли Фродо, Сем, Меррі та Піппін сиділи в Зеленому Драконі та пили пиво, вони вирішили зіграти в невелику гру з папером і ручкою, щоб визначити, хто купуватиме пиво в наступному раунді. Гра виглядає так:
Є прямокутна дошка розміром m \times n, де кожна клітинка позначена однією з літер W, I або N. Ваше завдання — знайти максимальну кількість тріоміно, які можна вирізати з дошки так, щоб клітинки W і N були на кінцях тріоміно, а I — посередині (тобто, щоб можна було прочитати WIN в певному порядку). Допустимі тріоміно — це послідовності з трьох клітинок, розташовані в ряд або під кутом. Той, хто знайде найбільшу кількість тріоміно, виграє і вказує, хто йде за пивом. Вам потрібно знайти максимальну кількість таких слів.
Складаються з декількох тестів. Кожен тест містить прямокутну сітку m \times n (1 \leq m, n \leq 30), що містить літери W, I та N. Тести відокремлюються один від одного порожнім рядком.
Для кожного тесту виведіть в окремому рядку максимальну кількість тріоміно, які можна вирізати з дошки.
Приклад 1