关灯问题

有一个$n\times m$的灯泡矩阵，一开始有的点是关（$0$），有的点是开（$1$）。

你可以每次可以操作一个坐标$(x,y)$，这个坐标及周围最多$4$个格子的$0$会变成$1$，$1$会变成$0$。

问：最少几次操作可以把整个矩阵全变成$0$，如果无法达成目标，输出$-1$。

输入格式

第一行$n,m(2\leq n\leq 1000,2\leq m\leq 1000)$。

接下来一个$n\times m$的矩阵，表示每个位置的初始状态（$0\leq a_{x,y} \leq 1$）。

前70分：时限4秒，后30分：时限1秒。

输出格式

如题所述。 本题保证解唯一。

样例输入1

3 3
0 1 0
1 1 1
0 1 0

样例输出1

1

样例解释

在坐标$(2,2)$操作一次即可。