타일 자르기

프로도, 샘, 메리, 피핀이 초록용 여관에서 에일을 마실 때, 다음 잔을 누가 살지 정하려고 양피지와 펜으로 간단한 놀이를 한다. 규칙은 다음과 같다.

각 칸에 문자 W, I, N 중 하나가 적힌 $m \times n$ 직사각형 타일($m$행 $n$열)이 주어진다. 이 타일에서 아래 조건을 만족하는 트리오미노(변으로 이어진 세 칸으로 이루어진 조각)를 최대 몇 개까지 잘라낼 수 있는지 구하여라.

• 조각의 양 끝 칸에는 W와 N이 하나씩 적혀 있어야 하고, 가운데 칸에는 I가 적혀 있어야 한다. 즉, 어떤 순서로 읽으면 WIN이 되어야 한다.
• 여기서 가운데 칸이란 나머지 두 칸 모두와 변으로 맞닿아 있는 칸을 뜻한다.
• 사용할 수 있는 조각 모양은 세 칸이 일직선으로 놓인 것과 ㄱ자(L자, 회전 포함) 두 가지뿐이다.

각 칸은 최대 하나의 조각에만 쓸 수 있다. 잘라낼 수 있는 조각의 최대 개수를 구하면 된다. 이 최댓값을 찾아낸 호빗이 이기고 누가 다음 잔을 살지 정한다.

참고: 샘과 피핀이 이 놀이에서 술값을 가장 자주 내는 편이라, 둘은 놀이를 바위·양피지·검(RPS)으로 바꾸자고 조르고 있다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 문자 W, I, N만으로 이루어진 $m \times n$ 격자이다($1 \le m, n \le 30$). 테스트 케이스 사이는 빈 줄로 구분되며, 입력은 파일의 끝(EOF)에서 종료된다.

각 테스트 케이스마다 잘라낼 수 있는 조각의 최대 개수를 정수 하나로 한 줄에 출력한다.