题目描述

司令部要在 N×M 的网格地图上部署炮兵部队。地图上每一格可能是山地（用 H 表示），也可能是平原（用 P 表示）。只有平原上可以部署炮兵，每格最多一支。

一支炮兵部队的攻击范围是：沿横向左右各两格，沿纵向上下各两格（十字形）。

要求任意两支炮兵部队都不在对方的攻击范围内。问最多能部署多少支炮兵部队。

输入格式

第一行两个正整数 N, M。 接下来 N 行，每行 M 个字符（P 或 H），中间没有空格，表示地图。

输出格式

一个整数，表示最多能部署的炮兵部队数量。

样例

输入

5 4
PHPP
PPHH
PPPP
PHPP
PHHP

输出

6

数据范围

1 ≤ N ≤ 100，1 ≤ M ≤ 10。