问题 K: Acowdemia III

Bessie 是一位忙碌的计算机科学研究生。

然而，即使是研究生也需要交友。

因此，Farmer John 开设了一片草地，目的是为了帮助 Bessie 与其他奶牛建立持久的友谊。

Farmer John 的草地可以被看做是由正方形方格组成的巨大二维方阵（想象一个巨大的棋盘）。

每个方格用如下字符标记：

• C，如果这个方格中有一头奶牛。
• G，如果这个方格中有草。
• .，如果这个方格既没有奶牛也没有草。

对于两头想要成为朋友的奶牛，她们必须选择在一个与她们均水平或竖直方向上相邻的有草方格见面。

在这个过程中，她们会在这个有草方格中吃草，所以之后的奶牛不能再使用这个方格作为见面地点。

一头奶牛可以与多头其他奶牛成为朋友，但是同一对奶牛不能见面并成为朋友多于一次。

Farmer John 希望有许多奶牛可以见面并成为朋友。

请求出当这一活动结束时在奶牛之间可以建立的朋友关系的最大数量。

输入格式

输入的第一行包含 N 和 M。

以下 N 行每行包含一个由 M 个字符组成的字符串，表示这个草地。

输出格式

输出在这一活动结束时在奶牛之间可以建立的朋友关系的最大数量。

数据范围

1≤N,M≤1000 

Bessie is a busy computer science graduate student. However, even graduate students need friends. As a result, Farmer John has opened a pasture with the explicit purpose of helping Bessie and other cows form lasting friendships.

Farmer John's pasture can be regarded as a large 2D grid of square "cells" (picture a huge chess board). Each cell is labeled with:

• C if the cell contains a cow.
• G if the cell contains grass.
• . if the cell contains neither a cow nor grass.

For two distinct cows to become friends, the cows must choose to meet at a grass-covered square that is directly horizontally or vertically adjacent to both of them. During the process, they eat the grass in the grass-covered square, so future pairs of cows cannot use that square as a meeting point. The same cow may become friends with more than one other cow, but no pair of cows may meet and become friends more than once.

Farmer John is hoping that numerous pairs of cows will meet and become friends over time. Please determine the maximum number of new friendships between distinct pairs of cows that can possibly be created by the end of this experience.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

4

If we label the cow in row ii and column jj with coordinates (i,j)(i,j), then in this example there are cows at (1,2)(1,2), (1,5)(1,5), (2,2)(2,2), (2,4)(2,4), (3,1)(3,1), (3,3)(3,3), (4,2)(4,2), (4,3)(4,3), and (4,5)(4,5). One way for four pairs of cows to become friends is as follows:

• The cows at (2,2)(2,2) and (3,3)(3,3) eat the grass at (3,2)(3,2).
• The cows at (2,2)(2,2) and (2,4)(2,4) eat the grass at (2,3)(2,3).
• The cows at (2,4)(2,4) and (3,3)(3,3) eat the grass at (3,4)(3,4).
• The cows at (2,4)(2,4) and (1,5)(1,5) eat the grass at (2,5)(2,5).

Problem credits: Benjamin Qi