#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N = 105;
int n, m;
// clear[i]: 第i个按钮把哪些灯强制关(置0)
// setv[i]: 第i个按钮把哪些灯强制开(置1)
int clearv[N], setv[N];
int dist[1100]; // 2^10=1024 个状态
int main() {
// 注意:输入格式第一行 n,第二行 m(不是同一行)
cin >> n >> m;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int x;
cin >> x;
if (x == 1) clearv[i] |= (1 << j); // 开->关
else if (x == -1) setv[i] |= (1 << j); // 关->开
}
}
int S = (1 << n) - 1; // 初始:全开
memset(dist, -1, sizeof(dist));
queue<int> q;
dist[S] = 0;
q.push(S);
while (!q.empty()) {
int s = q.front(); q.pop();
if (s == 0) break; // 全关
for (int i = 0; i < m; i++) {
// 先清掉要强制关的位,再置上要强制开的位
int ns = (s & ~clearv[i]) | setv[i];
if (dist[ns] == -1) {
dist[ns] = dist[s] + 1;
q.push(ns);
}
}
}
cout << dist[0] << endl;
return 0;
}
