当前没有测试数据。

关灯问题

题目描述

现有$n$盏灯，以及$m$个按钮。每个按钮可以同时控制这$n$盏灯一一按下了第$i$个按钮，对于所有的灯都有一个效果。按下$i$按钮对于第$j$盏灯，是下面$3$中效果之一：如果$a_{ij}$为$1$，那么当这盏灯开了的时候，把它关上，否则不管；如果为$-1$的话，如果这盏灯是关的，那么把它打开，否则也不管；如果是$0$，无论这灯是否开，都不管。

现在这些灯都是开的，给出所有开关对所有灯的控制效果，求问最少要按几下按钮才能全部关掉。

输入格式

前两行两个数，$n$，$m$。

接下来$m$行，每行$n$个数，$a_{ij}$表示第$i$个开关对第$j$个灯的效果。

输出格式

一个整数，表示最少按按钮次数。如果没有任何办法使其全部关闭，输出$-1$。

数据范围与提示

• 对于$20\%$的数据，$n < 5$；
• 对于$40\%$的数据，$m < 20$；
• 对于$100\%$的数据，$n \leq 10$，$m \leq 100$。

样例

3
2
1 0 1
-1 1 0

2