RT

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#define maxn 1010
using namespace std;
int n, m;

struct node { //每个城市
	int x;
	int y;
};

int _next[4][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
queue<node> q; //每一次搜完后清掉
int a[maxn][maxn]; //存图
int book[maxn][maxn]; //判定那些被访问了
bool conn[maxn]; //记录是否被连接
int con[maxn][maxn]; // 记录连接
//int shenfen[maxn][maxn];
int num[maxn] = {0};
//int l[maxn];
//int r[maxn];

void _reload() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			book[i][j] = 0;
		}
	}
	while (!q.empty()) {
		q.pop();
	}
	return;
}

void bfs(int x) { //用来搜索每个水厂的连接情况
	while (!q.empty()) {
		node z = q.front(); //先弹出一个结点
		q.pop();
		int tx, ty;
		if (z.x == n) {
			con[x][num[x]++] = z.y;
		}
		for (int i = 0; i < 4; i++) {
			tx = z.x + _next[i][0];
			ty = z.y + _next[i][1];
			if (tx > n || ty > m || ty < 1 || tx < 1 || book[tx][ty] == 1) {
				continue;
			}
			if (a[tx][ty] < a[z.x][z.y]) {
				book[tx][ty] = 1;
				q.push((node) {
					tx, ty
				});
			}
		}
	}
}
int book2[maxn];//泉水
int ans = 1145141;
int biao[maxn]; //显然这个用来找出最大的数

bool check() {
	for (int i = 1; i <= m; i++) {
		if (!conn[i]) {
			return false;
		}
	}
	return true;
}

void dfs(int num1) { //用来判断最少建几个厂
	if (check()) { //查一遍
		ans = min(ans, num1);
		return;
	}
//	bool ifOk = false;
	for (int i = 1; i <= m; i++) {
		if (!book2[i]) { //这个还没被搜到
			book2[i] = 1;
			//底下的是把周围水泵比自己小的标注上，用不着它们了
			int cur = i - 1;
			while (a[1][cur] < a[1][i] && cur >= 1) {
				if (book2[cur]) { //比你大我留着你？
					num1--;
				}
				book2[cur--] = 1; //标记
			}
			cur = i + 1;
			while (a[1][cur] < a[1][i] && cur <= m) {
				book2[cur++] = 1;
			}
			for (int j = 0; j <= num[i]; j++) {
				if (!conn[con[i][j]]) {
					conn[con[i][j]] = true;
				}
			}
			dfs(num1 + 1);
			for (int j = 0; j < num[i]; j++) {
				if (conn[con[i][j]]) {
					conn[con[i][j]] = false;
				}
			}
			cur = i - 1;
			while (a[1][cur] < a[1][i] && cur >= 1) {
				book2[cur--] = 0;
			}
			cur = i + 1;
			while (a[1][cur] < a[1][i] && cur <= m) {
				book2[cur++] = 0;
			}
			book2[i] = 0;
		}
	}

}

//void _find(int x) {
//	int mi = 1145141;
//	int ma = 0;
//	for (int i = 0; i < num[x]; i++) {
//		mi = min(mi, con[x][i]);
//		ma = max(ma, con[x][i]);
//	}
//	l[x] = mi;
//	r[x] = ma;
//}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> a[i][j];
		}
	}
//	sort(biao + 1, biao + n + 1);
	for (int i = 1; i <= m; i++) {
		q.push((node) {
			1, i
		});
		book[1][i] = 1;
		bfs(i);
		_reload();
	}
//	for (int i = 1; i <= m; i++) {
//		_find(i); //寻找线段区间
//	}
	for (int i = 1;  i <= m; i++) {
		for (int j = 0; j < num[i]; j++) {
			conn[con[i][j]] = true; //标记，用来寻找几个城市没连上
		}
	}
	int no = 0;
	bool ok = true;
	for (int i = 1; i <= m; i++) {
		if (conn[i] == false) {
			ok = false;
			no++;
		}
	}
	if (!ok) {
		cout << 0 << endl;
		cout << no;
	} else {
		memset(conn, false, sizeof(conn));
		dfs(0);
		cout << 1 << endl << ans;
	}

	return 0;
}