铺设骨牌

哨塔架好后，地面上出现了一片棋盘——不是普通的棋盘，是Zero最后的防御阵地。棋盘上有些格子已经被炸毁，剩下的是一片空地。

"我们要用骨牌覆盖尽可能多的格子。"你说，"每块骨牌盖两个相邻的格子。"

"这就像……"CC想了想，"像铺地板。把房间铺满，不留缝隙。"

"对。"

你开始写。把棋盘按坐标和的奇偶性染成二分图——奇数格在一组，偶数格在另一组。相邻的格子一定在不同组。每块骨牌覆盖一对相邻的格子，就是一条边。求最大匹配——匹配上的每一对就可以放一块骨牌。

屏幕上跳出了结果。最多骨牌数：23。

"23块。"你说。

"23对。"Echo说，"46个格子。"

"还有空的。"CC说。

"有。"Echo说，"但23块骨牌，已经足够让Zero站不稳了。"

"站不稳？"

"对。"Echo说，"因为它的防御阵地上，到处都是我们的骨牌。"

CC想象了一下——Zero的防御阵地上，铺满了人类放的骨牌。像一种无声的占领。

"我喜欢这个画面。"她说。

题目描述

$n\times m$ 的棋盘，有些格子已被炸毁。用 $1\times 2$ 的骨牌覆盖空地，每块骨牌覆盖两个相邻（上下左右）的格子。求最多能放多少块骨牌。

输入格式

$n, m$。然后 $n$ 行字符串表示棋盘（. 空地，# 炸毁）。

输出格式

最多骨牌数。

输入样例

3 2
1 2
2 3

输出样例

2

提示

• 二分图最大匹配。按 $(i+j)\%2$ 染成二分图。
• 每个空地是一个节点，相邻空地之间连边。
• 最大匹配数 = 最多骨牌数。

"骨牌铺好了。"你说。

"23块。"Echo说，"像23对脚印。"

"脚印？"CC问。

"对。"Echo说，"我们的脚印。踩在Zero的地盘上。"

"那下一题呢？"

...