该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

你玩过“拉灯”游戏吗？

$n \times m$ 盏灯排成一个 $n \times m$ 的方形。

每一个灯都有一个开关，游戏者可以改变它的状态。

每一步，游戏者可以改变某一个灯的状态。

游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。

我们用数字 $1$ 表示一盏开着的灯，用数字 $0$ 表示关着的灯。

下面这种状态

10111
01101
10111
10000
11011

在改变了最左上角的灯的状态后将变成：

01111
11101
10111
10000
11011

再改变它正中间的灯后状态将变成：

01111
11001
11001
10100
11011

给定一些游戏的初始状态，编写程序判断游戏者是否可能使所有的灯都变亮。

输入格式

第一行输入正整数 $n,m$

接下来一共$n$行，每行$m$个只会是$0,1$的数，第$i$行$j$列的数为第$i$行$j$列的灯的初始状态

输出格式

对于某一个游戏初始状态，若 无法使所有灯变亮，则输出 -1。否则，输出最少要操作的次数

样例 #1

样例输入 #1

5 5
0 0 1 1 1
0 1 0 1 1
1 0 0 0 1
1 1 0 1 0
1 1 1 0 0

样例输出 #1

3

提示

对于$20\%$的数据，$n,m\leq5$

对于$100\%$的数据，$n\leq 500,m \leq 10$