Kết Bạn Qua Cỏ

Cho một lưới $N\times M$ ô, mỗi ô là một trong ba loại:

• C: ô có bò
• G: ô có cỏ
• .: ô trống

Hai con bò có thể kết bạn bằng cách gặp nhau tại một ô cỏ kề cạnh (chung cạnh) với cả hai. Mỗi ô cỏ chỉ được sử dụng một lần. Mỗi lần sử dụng một ô cỏ, nó tạo ra đúng một cặp bạn.

Hãy tìm số cặp bạn nhiều nhất có thể tạo ra.

Dữ liệu vào

• Dòng 1: Hai số nguyên $N$ và $M$
• $N$ dòng tiếp theo: Chuỗi $M$ ký tự mô tả lưới

Dữ liệu ra

Một số nguyên duy nhất: số cặp bạn nhiều nhất.

Ràng buộc

• $1\le N,M\le 1000$

Ví dụ