Коров'яча академія III
Фермер Джон відкрив пасовище, щоб допомогти Бессі та її друзям.
Пасовище ФД можна уявити як велику двовимірну решітку квадратних клітинок. Кожна клітинка має один з наступних символів:
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).