题目描述

刘先生最近在学习国际象棋，使用一个叫 jloi-08 的游戏软件。在这个游戏里，不但可以和电脑普通地对弈，还可以学习著名的棋局，还有针对初学者的规则指导等丰富功能。但是…大小却要 1.4G T_T。

言归正传，在这个软件里，为了让玩家更好地理解和运用各个棋子，有很多趣味的游戏，比如以下就是一个：

给出一个棋盘和一些棋子，让你把这些棋子摆放在棋盘上，使得两两不互相攻击。你的得分由你摆放上去的棋子的个数与种类有关。

这个游戏很复杂，刘先生老是玩不到高分。于是电脑便降低了难度，替刘先生摆上了一些棋子，最后只给你任意多个 bishop（教主）。

现在刘先生便要考一考你，在电脑给出的这张棋盘上，最多能放几个 bishop。

国际象棋中一共有 6 种棋子：

• king（国王）；
• queen（皇后）；
• bishop（教主）；
• knight（骑士）；
• rook（车）；
• pawn（步兵）。

各棋子的攻击范围如下：

• queen 可以攻击与它在同一行，同一列，同一条对角线的棋子；
• knight 的攻击范围如下图所示：

• rook 攻击水平和垂直两条线上的所有格子；
• pawn 攻击前方两条斜线方向各一格(“前方”指 $x$ 递增的方向，$x$ 行 $y$ 列）；
• king 攻击周围 8 个方向各 1 格；
• bishop 攻击两条对角线上的所有格子。

除 knight 以外，所有棋子的攻击范围均会被别的棋子所阻挡。

可惜的是这个软件也不是顶优秀，给出的棋盘上的棋子可能互相会攻击，不过你不用理会这些，你只要保证你摆放的 bishop 不与它们以及不互相攻击就可以了。

输入格式

第一行是两个整数 $x,y$（$1 \leq x,y \leq 1024$）。

下面的 $x$ 行每行 $y$ 个字符表示棋盘。

其中：K – king，Q – queen，B – bishop，N – knight，R – rook，P – pawn，. – blank.

输出格式

仅一行一个数，表示最多能够摆放的 bishop 的个数。

3 3
..N
...
...

2

提示

BBN
...
...

BBN
...
B..

虽然看上去下面的方法比上面的优秀，但是 N 被第三行的 B 攻击了。也就是说，你需要避免的有 2 种情况： 你摆放的 bishop 之间的互相攻击以及你摆放的 bishop 与预先摆放好的棋子之间的互相攻击；但不用考虑预先摆放好的棋子之间的互相攻击。