var
i ,j, k ,n ,m, max, t, t1 : integer;
x, y : array[1..10] of integer;
begin
assign(input,'input.txt');reset(input);
assign(output,'output.txt');rewrite(output);
readln(n);
readln(m);
for i:=1 to m do
readln(x[i],y[i]);
max:=0;
for i:=1 to n do
for j:=1 to n do
begin
t:=2*n;
for k:=1 to m do
begin
t1:=abs(x[k]-i)+abs(y[k]-j);
if t1<t then t:=t1
end;
if t>max then max:=t
end;
write(max)
end.
i ,j, k ,n ,m, max, t, t1 : integer;
x, y : array[1..10] of integer;
begin
assign(input,'input.txt');reset(input);
assign(output,'output.txt');rewrite(output);
readln(n);
readln(m);
for i:=1 to m do
readln(x[i],y[i]);
max:=0;
for i:=1 to n do
for j:=1 to n do
begin
t:=2*n;
for k:=1 to m do
begin
t1:=abs(x[k]-i)+abs(y[k]-j);
if t1<t then t:=t1
end;
if t>max then max:=t
end;
write(max)
end.