题目描述

注意不同的内存限制。

给定一个黑白相间的矩形方格网格，我们将其复杂度定义如下：

• 如果所有方格都是黑色或都是白色，则复杂度为$0$。
• 否则，通过与网格边界平行的一条线将网格分成两个子网格，并称$c_1$和$c_2$为子网格的复杂度。可以有多种方法来进行划分，令$m$为这些划分中$\\max(c_1, c_2)$的最小值。网格的复杂度为$m+1$。

给定一个具有$H$行$W$列的网格，每个方格都是黑色或白色。从$A_{11}$到$A_{HW}$的$HW$个字符表示方格的颜色。如果位于自顶向下的第$i$行和自左向右的第$j$列的方格是黑色，则$A_{ij}$为#；如果方格是白色，则$A_{ij}$为.。

求给定网格的复杂度。

约束条件

• $1 \leq H,W \leq 185$
• $A_{ij}$为#或.。

输入

输入以以下格式从标准输入给出：

$H$ $W$ $A_{11}$$A_{12}$$...$$A_{1W}$ $:$ $A_{H1}$$A_{H2}$$...$$A_{HW}$

输出

输出给定网格的复杂度。

示例输入1

3 3
...
.##
.##

示例输出1

2

我们可以通过第一列和第二列之间的边界线将网格划分开来。第一列构成的子网格的复杂度为$0$，第二列和第三列构成的子网格的复杂度为$1$，所以整个网格的复杂度最多为$2$。

示例输入2

6 7
.####.#
#....#.
#....#.
#....#.
.####.#
#....##

示例输出2

4