Cho một bảng cờ kích thước \(R \times C\). Một số ô bị cấm (kí hiệu là \(\#\)), các ô còn lại trống (kí hiệu là \(.\)). Bạn cần đặt các quân domino kích thước \(1 \times 2\) lên bảng sao cho mỗi quân domino phủ đúng hai ô trống kề cạnh nhau (chung cạnh, không tính đường chéo), các quân domino không được chồng lên nhau. Hãy tìm số lượng quân domino tối đa có thể đặt được.

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên \(R, C\) (\(1 \le R, C \le 100\)).
• \(R\) dòng tiếp theo, mỗi dòng chứa \(C\) kí tự mô tả bảng. Kí tự \(.\) là ô trống, kí tự \(\#\) là ô bị cấm.

Định dạng đầu ra

• Một số nguyên duy nhất là số domino tối đa.

Ràng buộc

Ví dụ

Input:

3 3
...
.#.
...

Output:

4