I. I WIN
time limit per test
2 s
memory limit per test
256 megabytes
input
stdin
output
stdout

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.

Input

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

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

Examples
Input
4 4
WIIW
NNNN
IINN
WWWI
Output
5
Input
5 5
NINWN
INIWI
WWWIW
NNNNN
IWINN
Output
5