覆盖泥地

工厂旁边是一片泥地——不是普通的泥，是Zero排出的废料，黑色的，黏糊糊的。人踩上去会陷进去。

"我们要用木板盖住泥地。"你说，"每块木板可以盖一行或一列。用最少的木板，盖住所有泥地。"

"这就像……"CC想了想，"像铺地毯。把脏的地方盖住，眼不见为净。"

"对。"

你开始写。把泥地的行和列分成两组——行在左边，列在右边。如果某个格子是泥地，就在对应的行和列之间连一条边。求最小点覆盖——选最少的行和列，使得每条边至少有一个端点被选中。

屏幕上跳出了结果。最少木板数：7。

"七块。"你说。

"七块木板。"Echo说，"盖住七片泥地。"

"但泥还在下面。"CC说。

"在。"Echo说，"但眼不见为净。"

"这不是自欺欺人？"

"是。"Echo说，"但有时候，人需要自欺欺人才能活下去。"

CC没有反驳。她只是拿起一块木板，铺在泥地上。

"那我就自欺。"她说，"但只欺一会儿。等这一切结束了，我要把这些泥全挖出来，种上向日葵。"

"向日葵？"

"对。"CC说，"向着太阳的花。"

题目描述

$n\times m$ 的网格，有些格子是泥地。用木板覆盖泥地——每块木板可以覆盖整行或整列。求最少需要多少块木板。

输入格式

$n, m$。然后 $n$ 行字符串表示网格（* 泥地，. 空地）。

输出格式

最少木板数。

输入样例

3 2
1 2
2 3

输出样例

0

提示

• 二分图最小点覆盖。行在左，列在右，泥地格子对应边。
• 最小点覆盖 = 最大匹配（Kőnig定理）。
• 用匈牙利算法或Dinic求最大匹配。

"泥地盖住了。"你说。

"七块。"Echo说，"像七层被子。"

"七层被子？"CC笑了，"你怕冷？"

"不怕。"Echo说，"但我怕脏。" ...