program llx;
const dxx:array[1..4]of integer=(1,0,-1,0);
dyy:array[1..4]of integer=(0,1,0,-1);
var a,c:array[0..501,0..501]of longint;
b:array[1..500,1..2]of longint;
dx,dy:array[1..250000]of longint;
f:array[0..500]of longint;
s,t,i,j,n,m,k,o,p:longint;
function min(i,j:longint):longint;
begin
if i<j then exit(i) else exit(j);
end;
begin
readln(n,m);
for i:=1 to m do b[i,1]:=maxlongint;
for i:=0 to n+1 do
for j:=0 to m+1 do
begin
if (i*j=0)or(i>n)or(j>m) then a[i,j]:=10000000 else read(a[i,j]);
end;
for i:=1 to m do
begin
s:=0;
t:=1;
dx[t]:=1;
dy[t]:=i;
fillchar(c,sizeof(c),0);
c[1,i]:=1;
repeat
inc(s);
for j:=1 to 4 do
if (c[dx[s]+dxx[j],dy[s]+dyy[j]]=0)and(a[dx[s],dy[s]]>a[dx[s]+dxx[j],dy[s]+dyy[j]]) then
begin
inc(t);
dx[t]:=dx[s]+dxx[j];
dy[t]:=dy[s]+dyy[j];
c[dx[t],dy[t]]:=1;
if dx[t]=n then
begin
f[dy[t]]:=1;
if dy[t]>b[i,2] then b[i,2]:=dy[t];
if dy[t]<b[i,1] then b[i,1]:=dy[t];
end;
end;
until s=t;
end;
for i:=1 to m do if f[i]=1 then inc(o);
if o<m then begin writeln(0);writeln(m-o);end;
fillchar(f,sizeof(f),0);
f[0]:=0;
for i:=1 to m do
begin
f[i]:=1000000;
for j:=1 to m do
if (b[j,1]<=i)and(b[j,2]>=i) then
f[i]:=min(f[i],f[b[j,1]-1]+1);
end;
writeln(1);
writeln(f[m]);
end.