#include <stdlib.h>
#include <stdio.h>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAX_N	1000
#define MAX_M	10
#define MAX_K	20


int N, M, K;
int A[MAX_N][MAX_M];
int results[MAX_N][MAX_N];
int sums[MAX_M];
bool datas[MAX_N][MAX_N];
unsigned long long bitmasks[MAX_N][MAX_K];
unsigned long long bitmask1[MAX_K];
unsigned long long bitmask2[MAX_K];
int maxvalue1, maxvalue2;
int maxleft1, maxright1;
int maxleft2, maxright2;


void S(unsigned long long* arr, int idx)
{
	arr[idx / 64] |= (1ULL << (idx % 64));
}


bool And(unsigned long long* arr1, unsigned long long* arr2, int start, int end)
{
	int s = start / 64, e = end / 64;

	for (int i = s; i <= e; ++i) {
		if (arr1[i] & arr2[i]) return true;
	}
	return false;
}


int calc()
{
	K = N / 64 + 2;

	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			sums[j] = 0;
		}
		for (int j = i; j < N; ++j) {
			for (int k = 0; k < M; ++k) {
				sums[k] += A[j][k];
			}
			int m = INT_MIN, idx = -1;
			for (int k = 0; k < M; ++k) {
				if (sums[k] >= m) {
					m = sums[k];
					idx = k;
				}
			}
			datas[i][j] = idx == 0;
		}
	}

	for (int i = 0; i < N; ++i) {
		results[0][i] = datas[i][N - 1] ? 1 : -1;
	}

	memset(bitmasks, 0, sizeof(bitmasks));
	for (int i = 0; i < N; ++i) {
		for (int j = i; j < N; ++j) {
			if (datas[i][j]) {
				S(bitmasks[i], j);
			}
		}
	}

	for (int i = 1; i < N; ++i) {
		maxvalue1 = maxvalue2 = INT_MIN;
		memset(bitmask1, 0, K * 8);
		memset(bitmask2, 0, K * 8);

		for (int j = N - 1 - i; j >= 0; --j) {
			int x = results[i - 1][j + 1];
			if (x > maxvalue1) {
				memcpy(bitmask2, bitmask1, K * 8);
				maxvalue2 = maxvalue1;
				maxleft2 = maxleft1;
				maxright2 = maxright1;

				memset(bitmask1, 0, K * 8);
				maxvalue1 = x;
				maxleft1 = maxright1 = j;
				S(bitmask1, j);
			}
			else if (x == maxvalue1) {
				maxleft1 = j;
				S(bitmask1, j);
			}
			else if (x > maxvalue2) {
				memset(bitmask2, 0, K * 8);
				maxvalue2 = x;
				maxleft2 = maxright2 = j;
				S(bitmask2, j);
			}
			else if (x == maxvalue2) {
				maxleft2 = j;
				S(bitmask2, j);
			}

			if (And(bitmasks[j], bitmask1, maxleft1, maxright1)) {
				results[i][j] = maxvalue1 + 1;
			}
			else {
				if(maxvalue2 > INT_MIN && And(bitmasks[j], bitmask2, maxleft2, maxright2)) {
					results[i][j] = max(maxvalue1 - 1, maxvalue2 + 1);
				}
				else {
					results[i][j] = maxvalue1 - 1;
				}
			}
		}
	}

	for (int i = N - 1; i >= 0; --i) {
		if (results[i][0] > 0) {
			return N - i - 1;
		}
	}
	return -1;
}


int main()
{
	scanf_s("%d %d", &N, &M);
	while (N < 2 || N > MAX_N || M < 2 || M > MAX_M) printf("...");

	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			scanf_s("%d", &A[i][j]);
		}
	}

	printf("%d\n", calc());
	return 0;
}