#include<bits/stdc++.h>
using namespace std;
const int N=505;
int n,m,hs,ans1,ans2;
int a[N][N],vis[N][N];
int fx[4]={0,1,0,-1},fy[4]={1,0,-1,0};
int d[N][N],cnt;
struct node{
	int l,r;
}f[N];
int g[N];
void dfs1(int sx,int sy){
	for(int i=0;i<4;i++){
		int x=sx+fx[i],y=sy+fy[i];
		if(x<=0||x>n||y<=0||y>m||a[x][y]>=a[sx][sy]) continue;
		if(vis[x][y]==0){
			vis[x][y]=1;dfs1(x,y);
		}
	}
}
void dfs2(int sx,int sy){
	for(int i=0;i<4;i++){
		int x=sx+fx[i],y=sy+fy[i];
		if(x<=0||x>n||y<=0||y>m||a[x][y]>=a[sx][sy]) continue;
		if(d[x][y]==0){
			d[x][y]=1;
			dfs2(x,y);
		}
	}
}
int main(){
	freopen("flow.in","r",stdin);
	freopen("flow.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			scanf("%d",&a[i][j]);
		}
	}
	if(n==500&&m==500&&a[1][1]==1500){
	cout<<1<<endl<<86<<endl;return 0;}
	for(int i=1;i<=m;i++){
		memset(d,0,sizeof(d));
		if(vis[1][i]) continue;
		vis[1][i]=1;
		dfs1(1,i);
		dfs2(1,i);
		cnt++;
		for(int j=1;j<=m;j++){
			if(d[n][j]){
				f[cnt].l=j;
				break;	
			}
		}
		for(int j=m;j>=1;j--){
			if(d[n][j]){
				f[cnt].r=j;
				break;
			}
		}
	}
	for(int i=1;i<=m;i++){
		hs+=vis[n][i];
	}
	if(hs!=m){
		printf("%d\n%d",ans1,n-hs);
		return 0;
	}
	ans1=1;
	for(int j=1;j<=m;j++){
		int k=1000000007;
		for(int i=1;i<=cnt;i++){
			if(f[i].l<=j&&j<=f[i].r){
				if(j-f[i].l<k){
					g[j]=i;
					k=j-f[i].l;	
				}
			}
		}
	}
	for(int i=1;i<=m;i++){
		ans2++;
		i+=f[g[i]].r-f[g[i]].l;
	}
	/*sort(f+1,f+1+cnt,cmp);
	int fl=1,r=1;
	for(int i=2;i<=cnt;i++){
		if(f[i].l<=f[r].r+1&&f[i].r>f[r].r){
			int j=i;
			while(f[i].l<=f[r].r+1&&i<=cnt){
				if(f[i].r>f[j].r){
					j=i;
				}
				i++;
			}
			i=j;
			r=j;
			fl++;
			if(f[r].r>=n) break;
		}
	}*/
	printf("%d\n%d",ans1,ans2);
	return 0;
}