题目描述

司令部的将军们计划在一个 $N \times M$ 的网格地图上部署炮兵部队。地图的每个格子可能是山地（用 'H' 表示），也可能是平原（用 'P' 表示）。在平原上可以部署炮兵部队，而山地不能部署。

一支炮兵部队的攻击范围是：

• 横向：左右各两格（共覆盖 $5$ 列）。
• 纵向：上下各两格（共覆盖 $5$ 行）。

部署规则：

1. 任何两支炮兵部队不能互相攻击，即任意一支炮兵部队的攻击范围内不能有其他炮兵部队。
2. 目标是最大化部署的炮兵数量。
   

输入格式

• 第一行：两个整数 $N$ 和 $M$（$N \leq 100$，$M \leq 10$）。
• 接下来的 $N$ 行：每行 $M$ 个字符（'P' 或 'H'），表示地图。

输出格式

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

示例输入

5 4
PHPP
PPHH
PPPP
PHPP
PHHP

示例输出

6

题目来源

NOI 2001