在 ICPC 比赛中惨败后，Matvey 决定去粉刷栅栏。

他的任务是将一个（据说是“小”的）栅栏刷成黑色。栅栏是一个大小为 $n \times m$ 的网格矩形。每个格子可以是白色或黑色。初始颜色已知。

Matvey 可以使用以下操作进行粉刷：

• 选择一条沿网格边缘且穿过矩形的水平或垂直直线。
• 在所选直线的一侧，保持颜色不变。
• 在所选直线的另一侧，首先将所有格子刷成白色。然后，在该侧，将所有关于所选直线对称的格子为黑色的格子刷成黑色。

请问将所有格子刷成黑色所需的最少操作次数是多少？

输入格式

第一行包含两个整数 $n, m$ ($1 \le n \cdot m \le 10^6$)，表示栅栏的大小。 接下来的 $n$ 行，每行包含一个由 $m$ 个字符（0 或 1）组成的字符串。如果第 $i$ 行的第 $j$ 个字符为 0，则第 $i$ 行第 $j$ 列的格子为白色。否则，该格子为黑色。 保证至少存在一个黑色格子。

输出格式

输出一个整数，表示将所有格子刷成黑色所需的最少操作次数。

样例

输入格式 1

4 4
1001
0100
0110
0110

输出格式 1

3

说明

第一个测试用例中将所有格子刷成黑色的过程如下图所示。