program ppg;
var
  i,j,n,top,p:longint;
  sz:array[1..50,1..2]of longint;
  s:array[1..50]of set of 1..50;
  t:array[0..2500,1..3]of longint;
procedure qsort(a,b:longint);
var
  p1,p2:longint;
begin
  if a<b then begin
    t[0]:=t[a];
    p1:=a;
    p2:=b;
    while p1<p2 do
    begin
      while (p1<p2)and(t[0,3]<t[p2,3]) do
        p2:=p2-1;
      if p1<p2 then begin
        t[p1]:=t[p2];
        p1:=p1+1;
      end;
      while (p1<p2)and(t[0,3]>t[p1,3]) do
        p1:=p1+1;
      if p1<p2 then begin
        t[p2]:=t[p1];
        p2:=p2-1;
      end;
    end;
    t[p1]:=t[0];
    qsort(a,p1-1);
    qsort(p1+1,b);
  end;
end;
begin
  assign(input,'ppg.in');
  assign(output,'ppg.out');
  reset(input);
  rewrite(output);
  readln(n);
  for i:=1 to n do
    readln(sz[i,1],sz[i,2]);
  top:=0;
  for i:=1 to n-1 do
    for j:=i+1 to n do
    begin
      top:=top+1;
      t[top,1]:=i;
      t[top,2]:=j;
      t[top,3]:=(abs(sz[j,1]-sz[i,1])+abs(sz[j,2]-sz[i,2]))div 2;
      if (abs(sz[j,1]-sz[i,1])+abs(sz[j,2]-sz[i,2])) mod 2<>0 then t[top,3]:=t[top,3]+1;
    end;
  qsort(1,top);
  for i:=1 to n do
    s[i]:=[i];
  for i:=1 to top do
  begin
    s[t[i,1]]:=s[t[i,1]]+s[t[i,2]];
    s[t[i,2]]:=s[t[i,2]]+s[t[i,1]];
    p:=0;
    for j:=1 to n do
      if not(j in s[t[i,1]]) then begin
        p:=1;
        break;
      end;
    if p=0 then begin
      writeln(t[i,3]);
      break;
    end;
  end;
  close(input);
  close(output);
end.