1035. 十字绣

时间限制: 0.5 second

内存限制: 64 MB

问题描述

考古学家发现了一块装饰有刺绣的布料。这种刺绣是用几根线制作的十字绣。观察到以下规则：

• 布料有一个带正方形单元格的网格。

• 每个针脚覆盖网格一个单元格的对角线。针脚可以位于布料的两面，但每个针脚只位于布料的一面（线只能在网格顶点处开始、结束和穿过布料）。

• 在布料的每一面，每个单元格的每条对角线上最多只能有一个针脚。

• 每根线由几个交替排列在布料不同面的针脚组成。（这意味着由一根线形成的两个连续针脚位于布料的不同面，并在网格顶点处连接）

• 针只能在网格顶点处穿过布料。

在图中你可以看到一个由六个针脚组成的图案示例。网格大小为 $4 \times 5$。布料的正面绘制在图形的上半部分。位于正面的针脚用实线绘制。未被正面针脚覆盖的背面针脚用点线绘制。在图形的下半部分，布料的朝向与上半部分相同。所有背面针脚在那里都用实线绘制。不覆盖背面针脚的正面针脚用点线绘制。这个十字绣不能用少于四根线制作。

考古学家想知道这个图案是否是用最少数量的线制作的。你需要编写一个程序，确定制作给定图案所需的最少线程数。

输入

第一行包含整数 $N$ 和 $M$，分别是网格的垂直（$N$）和水平（$M$）尺寸（$1 \leq N, M \leq 200$）。

接下来的 $2N$ 行每行包含 $M$ 个符号。每个符号描述网格的一个方格。前 $N$ 行对应布料的正面，后 $N$ 行对应布料的背面。使用的符号是 ".", "/", "" 和 "X"（点表示空方格）。

更多信息请参见样例。它对应于图中绘制的布料。

输出

输出制作所述图案所需的最少线程数。

样例

输入

4 5
.....
.\...
..\..
.....
.....
....\
.\X..
.....

输出

4