该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

描述

有一个N*M的棋盘，棋盘的每一格是三种类型之一：空地、草地、墙。机器人只能放在空地上。在同一行或同一列的两个机器人，若它们之间没有墙，则它们可以互相攻击。问给定的棋盘，最多可以放置多少个机器人，使它们不能互相攻击

如图，白色表示空地，绿色表示草地，黑色表示墙。

格式

输入格式

第1行为两个整数N、M。

接下来N行，每行M个大写字母（只可能是’E’、’G’或’W’,E表示空地，G表示草地，W表示墙壁）。

输出格式

一个整数N，表示最多能放置N个机器人。

样例1

样例输入1

5 5
EGGGW
GWWWG
EEWEE
GGGWE
WEGGE

样例输出1

4

限制

各个测试点1s

提示

对于20%的数据，保证N≤10，M≤10，且空地≤26。

对于100%的数据，保证N≤100，M≤100。