f,v,i,j,k,c,d,m:longint;

procedure print(i,j:longint);

var n:integer;

begin

if i>0 then

begin

n:=i;

while a[i,n]<>j do n:=n+1;

print(i-1,j-b[i,n]);

write(n,' ');

end;

end;

begin

readln(f,v);

for i:=1 to f do

for j:=1 to v do read(b[i,j]);

c:=b[1,1];

for i:=2 to v do

if c<b[1,i] then

begin

a[1,i]:=b[1,i];

c:=b[1,i];

end

else a[1,i]:=c;

for i:=2 to f do

for j:=i to v-f+i do

begin

c:=-maxlongint;

for k:=i-1 to j-1 do

begin

d:=-maxlongint;

for m:=k+1 to j do

if b[i,m]>d then d:=b[i,m];

if d+a[i-1,k]>c then c:=d+a[i-1,k];

end;

a[i,j]:=c

end;

c:=-maxlongint;

for i:=f to v do

begin

if a[f,i]>c then c:=a[f,i];

end;

writeln(c);

print(f,c)

end.