#561. 猫娘部署

公元 2225 年，为满足广大同学的精神需求，车南大学资产管理处投资 5000 万元，拟将车南大学广寒宫校区的猫猫升级为猫娘。

车南大学广寒宫校区可以视为一个 $n$ 行 $m$ 列的二维网格，每个格子有两种状态：有猫（Y）和无猫（N）。

显然，猫娘必须在有猫地区部署；并且，由于猫娘需要更加良好的饲养环境，任意两只猫娘不能相邻。定义相邻为上下左右四个格子相邻。

同学们希望猫娘的数量尽可能多，请你计算出猫娘的最大数量。

第一行两个整数 $n,m(1 \le n, m \le 8)$，表示网格大小。

接下来 $n$ 行，每行一个长度为 $m$ 的字符串，表示网格。

输出一个整数，表示猫娘的最大数量。

样例解释

在 $(1, 2), (1, 4), (2, 1), (3, 2), (3, 4), (4, 1), (4, 3)$ 位置部署猫娘可以最大部署 $7$ 只猫娘。