Tile Cut

When Frodo, Sam, Merry, and Pippin are drinking ale at the Green Dragon Inn, they play a little game with parchment and pen to decide who buys the next round. The rules are as follows.

You are given an $m \times n$ rectangular tile ($m$ rows and $n$ columns) in which every square is marked with one of the letters W, I, and N. Find the maximum number of triominoes (pieces made of three edge-connected squares) that can be cut from this tile subject to the following rules:

• The two end squares of a piece must read W and N (one each), and the middle square must read I. In other words, the piece spells WIN when read in some order.
• The middle square is the one that shares an edge with both of the other two squares.
• Only two piece shapes are allowed: three squares in a straight line, and the ell-shaped piece (an L, in any of its four rotations).

Each square may belong to at most one piece. Report the maximum number of pieces that can be cut. The Hobbit who finds this maximum wins and decides who buys the next round.

Side note: Sam and Pippin tend to buy the most rounds when they play this game, so they are lobbying to switch to Rock, Parchment, Sword (RPS)!

The input consists of multiple test cases. Each test case is an $m \times n$ grid ($1 \le m, n \le 30$) containing only the letters W, I, and N. Test cases are separated by a blank line, and the input is terminated by end-of-file (EOF).

For each test case, print a single integer on its own line: the maximum number of pieces that can be cut.