问题描述

给定一个具有 $H$ 行和 $W$ 列的矩阵 $A$。其每个元素的值为 $0$ 或 $1$。对于整数对 $(i, j)$，其中 $1 \leq i \leq H$ 且 $1 \leq j \leq W$，我们将 $A_{i,j}$ 表示为第 $i$ 行和第 $j$ 列的元素。

您可以对矩阵 $A$ 执行以下操作任意次数（可能为零）：

• 选择一个整数 $i$，使得 $1 \leq i \leq H$。对于每个整数 $j$，使得 $1 \leq j \leq W$，将 $A_{i,j}$ 的值替换为 $1-A_{i,j}$。

如果 $A_{i,j}$ 孤立，则说明没有相邻元素具有相同的值；换句话说，当且仅当四个整数对 $(x,y) = (i-1,j),(i+1,j),(i,j-1),(i,j+1)$ 不满足 $1 \leq x \leq H, 1 \leq y \leq W$ 和 $A_{i,j} = A_{x,y}$ 时，$A_{i,j}$ 就是孤立的。

判断是否可以通过重复操作使矩阵 $A$ 中没有元素是孤立的。如果可能，找出所需操作的最小次数。

约束条件

• $2 \leq H, W \leq 1000$
• $A_{i,j} = 0$ 或 $A_{i,j} = 1$
• 输入中的所有值都是整数。

输入

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

$H$ $W$ $A_{1,1}$ $A_{1,2}$ $\ldots$ $A_{1,W}$ $A_{2,1}$ $A_{2,2}$ $\ldots$ $A_{2,W}$ $\vdots$ $A_{H,1}$ $A_{H,2}$ $\ldots$ $A_{H,W}$

输出

如果可以通过重复操作使其不再有孤立元素，则输出所需操作的最小次数；否则输出 -1。

示例输入 1

3 3
1 1 0
1 0 1
1 0 0

示例输出 1

1

通过选择 $i = 1$ 进行一次操作，我们得到 $A = ((0,0,1),(1,0,1),(1,0,0))$，其中不再存在孤立元素。

示例输入 2

4 4
1 0 0 0
0 1 1 1
0 0 1 0
1 1 0 1

示例输出 2

2

示例输入 3

2 3
0 1 0
0 1 1

示例输出 3

-1