Фермер Джон открыл пастбище с целью помочь Беси и её друзьям.
Пастбище ФД можно рассматривать как большую 2D-решётку квадратных ячеек. Каждая ячейка помечена таким образом:
C если в ячейке корова
G если в ячейке трава
. если в ячейке нет ни коровы, ни травы
Для того, чтобы две различные коровы стали друзьями, коровы должны встретиться в ячейке с травой, которая горизонтально или вертикально соседствует с каждой из них. Во время этого процесса они съедают траву в этой ячейке, поэтому другая пара коров уже не сможет использовать эту ячейку как место встречи. Любая корова может подружиться более чем с одной другой коровой, но никакая пара коров не может встретиться и стать друзьями более одного раза.
ФД надеется, что много пар коров станут друзьями. Определите максимальное количество пар коров, которые могут стать друзьями.
Первая строка содержит n и m (n, m ≤ 1000).
Каждая из следующих n строк содержит m символов, описывая пастбище.
Определите максимальное количество пар коров, которые могут стать друзьями.
Если мы пометим корову в строке i и столбце j координатами (i, j), тогда в этом примере есть коровы в (1, 2), (1, 5), (2, 2), (2, 4), (3, 1), (3, 3), (4, 2), (4, 3) и (4, 5). Один из способов, чтобы 4 коровы стали друзьями таков:
Коровы из (2, 2) и (3, 3) едят траву в (3, 2).
Коровы из (2, 2) и (2, 4) едят траву в (2, 3).
Коровы из (2, 4) и (3, 3) едят траву в (3, 4).
Коровы из (2, 4) и (1, 5) едят траву в (2, 5).