400550: GYM100203 I I WIN

Given an n × m rectangular tile with each square marked with one of the letters W, I, and N, find the maximal number of triominoes that can be cut from this tile such that the triomino has W and N on the ends and I in the middle (that is, it spells WIN in some order). Of course the only possible triominoes are the one with three squares in a straight line and the L-shaped ones, and the triominoes can't overlap.

First line contains two integers n and m with 1 ≤ m, n ≤ 22. The next n lines contain m characters each (only the letters W, I and N).

Output a single integer: the maximum number of nonoverlapping WIN-triominoes.

4 4
WIIW
NNNN
IINN
WWWI

5

5 5
NINWN
INIWI
WWWIW
NNNNN
IWINN

5