import sys input = sys.stdin.readline N = int(input()) P = [list(map(int, input().split())) for _ in [0] * N] st = set([0]) dist = [[0] * (N - i) for i in range(N)] for i in range(N - 1): for j in range(i + 1, N): dist[i][j - i] = abs(P[i][0] - P[j][0]) + abs(P[i][1] - P[j][1]) st.add(dist[i][j - i]) def func(k): c = [0] * N for v in range(N): if(c[v]): continue c[v] = 1 que = [v] while(que): now = que.pop() for nv, nd in route[now]: if(nd <= lis[k]): continue if(c[nv] == 0): c[nv] = -c[now] que.append(nv) elif(c[nv] == c[now]): return False return True route = [[] for _ in [0] * N] used = [[0] * (N - i) for i in range(N)] lis = sorted(st)[::-1] ok = 0 ng = len(lis) while(ng - ok > 1): k = (ok + ng) // 2 for i in range(N - 1): for j in range(i + 1, N): if(used[i][j - i] or dist[i][j - i] <= lis[k]): continue used[i][j - i] = 1 route[i].append((j, dist[i][j - i])) route[j].append((i, dist[i][j - i])) if(func(k)): ok = k else: ng = k ans = lis[ok] // 2 print(ans)