本题使用标准输入、标准输出，无需读写题面中提到的文件。

题目描述

Bessie 是一名忙碌的计算机科学研究生。然而，即使是研究生也需要朋友。因此，农夫约翰开辟了一片牧场，明确目的是帮助 Bessie 和其他奶牛建立持久的友谊。

农夫约翰的牧场可以看作是一个由方形“格子”组成的巨大二维网格（想象一张巨大的棋盘）。每个格子标记为： C：该格子里有一头牛。 G：该格子里有草。 .：该格子里既没有牛也没有草。

为了让两头不同的牛成为朋友，这两头牛必须选择在一个长草的格子上见面，并且该格子需要与它们两者都直接水平或垂直相邻。在这个过程中，它们会吃掉该格子里的草，因此之后的牛对将不能再使用该格子作为见面地点。

同一头牛可以与多头其他牛成为朋友，但任意一对牛不能见面并成为朋友超过一次。

农夫约翰希望随着时间推移，会有许多对奶牛见面并成为朋友。请你确定，到这次经历结束时，不同奶牛对之间最多可能产生多少个新的友谊关系。

输入格式

第一行包含 $N$ 和 $M$（$N,M \leq 1000$）。 接下来 $N$ 行每行包含一个长度为 $M$ 的字符串，用于描述牧场。

输出格式

输出在这次经历结束时，最多能成为朋友的奶牛对数。

4 5
.CGGC
.CGCG
CGCG.
.CC.C

4

提示

如果我们将第 $i$ 行第 $j$ 列的牛用坐标 $(i,j)$ 表示，那么在本例中，牛位于 $(1,2)$、$(1,5)$、$(2,2)$、$(2,4)$、$(3,1)$、$(3,3)$、$(4,2)$、$(4,3)$ 和 $(4,5)$。一种让四对奶牛成为朋友的方法如下： 位于 $(2,2)$ 和 $(3,3)$ 的奶牛吃掉 $(3,2)$ 的草。 位于 $(2,2)$ 和 $(2,4)$ 的奶牛吃掉 $(2,3)$ 的草。 位于 $(2,4)$ 和 $(3,3)$ 的奶牛吃掉 $(3,4)$ 的草。 位于 $(2,4)$ 和 $(1,5)$ 的奶牛吃掉 $(2,5)$ 的草。

评分： 测试点 2-4 满足 $N=2$。 测试点 5-12 没有额外限制。

题目来源：Benjamin Qi

来源

USACO|2021|Bronze