#include <bits/stdc++.h>
using namespace std;

#define rand() (rand() | rand() << 16)

#define INF (INT_MAX - 5)

int prim(vector<vector<pair<int, int>>>& graph, int startVertex) {
    int N = graph.size();
    // Priority queue to store the edges and their weights
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    // Create a vector to track visited vertices
    vector<bool> visited(N, false);
    // Add the starting vertex to the priority queue
    pq.push(make_pair(0, startVertex));
    vector<pair<int, int>> mst;  // Minimum spanning tree
    while (!pq.empty()) {
        // Extract the minimum weight edge from the priority queue
        pair<int, int> curr = pq.top();
        pq.pop();
        int weight = curr.first;
        int vertex = curr.second;
        if (visited[vertex]) {
            continue;
        }
        // Mark the current vertex as visited
        visited[vertex] = true;
        // Add the current edge to the minimum spanning tree
        mst.push_back(make_pair(weight, vertex));
        // Iterate through all adjacent vertices of the current vertex
        for (pair<int, int>& edge : graph[vertex]) {
            int adjVertex = edge.first;
            int adjWeight = edge.second;
            if (!visited[adjVertex]) {
                // Add the adjacent vertex and its weight to the priority queue
                pq.push(make_pair(adjWeight, adjVertex));
            }
        }
    }
    // Find the maximum weight among the edges in the MST
    int maxWeight = 0;
    for (pair<int, int>& edge : mst) {
        maxWeight = max(maxWeight, edge.first);
    }
    return maxWeight;
}

struct Pt { int x, y; };

int c0(Pt p) { return - p.x + p.y; }
int c1(Pt p) { return + p.x - p.y; }
int c2(Pt p) { return - p.x - p.y; }
int c3(Pt p) { return + p.x + p.y; }
int c4(Pt p) { return + p.x - p.y; }
int c5(Pt p) { return - p.x + p.y; }
int c6(Pt p) { return + p.x + p.y; }
int c7(Pt p) { return - p.x - p.y; }

int d0(Pt p) { return + p.x + p.y; }
int d1(Pt p) { return + p.x + p.y; }
int d2(Pt p) { return - p.x + p.y; }
int d3(Pt p) { return - p.x + p.y; }
int d4(Pt p) { return - p.x - p.y; }
int d5(Pt p) { return - p.x - p.y; }
int d6(Pt p) { return + p.x - p.y; }
int d7(Pt p) { return + p.x - p.y; }

int l0(Pt p) { return p.y;	}
int h0(Pt p) { return INF;	}

int l1(Pt p) { return p.x;	}
int h1(Pt p) { return INF;	}

int l2(Pt p) { return -INF;	}
int h2(Pt p) { return p.x;	}

int l3(Pt p) { return p.y;	}
int h3(Pt p) { return INF;	}

int l4(Pt p) { return -INF;	}
int h4(Pt p) { return p.y;	}

int l5(Pt p) { return -INF;	}
int h5(Pt p) { return p.x;	}

int l6(Pt p) { return p.x;	}
int h6(Pt p) { return INF;	}

int l7(Pt p) { return -INF;	}
int h7(Pt p) { return p.y;	}

int (* cv[8])(Pt p) = {c0, c1, c2, c3, c4, c5, c6, c7};
int (* dv[8])(Pt p) = {d0, d1, d2, d3, d4, d5, d6, d7};
int (* lv[8])(Pt p) = {l0, l1, l2, l3, l4, l5, l6, l7};
int (* hv[8])(Pt p) = {h0, h1, h2, h3, h4, h5, h6, h7};
int (* ev[8])(Pt p) = {l0, l1, h2, l3, h4, h5, l6, h7};

int dist(Pt a, Pt b) { return abs(a.x - b.x) + abs(a.y - b.y); }

int bsgi(const vector<Pt>& v,  const vector<int>& vi, int (* e)(Pt p), int x) {
	int l = 0, h = vi.size();
	while (l != h) {
		int m = (l + h) / 2;
		if (e(v[vi[m]]) > x) {
			h = m;
		}
		else {
			l = m + 1;
		}
	}
	return h;
}

int bsli(const vector<Pt>& v, const vector<int>& vi, int (* e)(Pt p), int x) {
	int l = -1, h = vi.size() - 1;
	while (l != h) {
		int m = (l + h + 1) / 2;
		if (e(v[vi[m]]) < x) {
			l = m;
		}
		else {
			h = m - 1;
		}
	}
	return h;
}

int main() {
	int N = 40000;
	cin >> N;
	vector<Pt> v(N);
	vector<int> w(N);
	iota(w.begin(), w.end(), 0);
	vector<vector<pair<int, int>>> g(N);
	vector<vector<int>> st(N * 4);
	vector<vector<int>> pref(N * 4);
	for (int i = 0; i < N; i++) {
//		v[i].x = rand() % 1000000000 + 1, v[i].y = rand() % 1000000000 + 1;
		cin >> v[i].x >> v[i].y;
	}
	for (int q = 0; q < 8; q++) {
		if (q == 0 || q == 3 || q == 4 || q == 7) {
			sort(w.begin(), w.end(), [&](auto a, auto b) { return v[a].y < v[b].y; });
		}
		else {
			sort(w.begin(), w.end(), [&](auto a, auto b) { return v[a].x < v[b].x; });
		}
		function<void(int, int, int)> init = [&](int i, int l, int r) {
			st[i].assign(w.begin() + l, w.begin() + r + 1);
			sort(st[i].begin(), st[i].end(), [&](auto a, auto b) { return cv[q](v[a]) < cv[q](v[b]); });
			pref[i].resize(r - l + 1);
			for (int j = 0, m = j; j < r - l + 1; j++) {
				if (dv[q](v[st[i][j]]) < dv[q](v[st[i][m]])) {
					m = j;
				}
				pref[i][j] = st[i][m];
			}
			if (l == r) {
				return;
			}
			init(i * 2 + 1, l, (l + r) / 2);
			init(i * 2 + 2, (l + r) / 2 + 1, r);
		};
		init(0, 0, N - 1);
		for (int p = 0; p < N; p++) {
			int L = bsgi(v, w, ev[q], lv[q](v[p]) - (q % 2 == 0));
			int R = bsli(v, w, ev[q], hv[q](v[p]) + (q % 2 == 0));
			if (L > R) {
				continue;
			}
			int res = -1;
			function<void(int, int, int)> query = [&](int i, int l, int r) {
				if (r < L || l > R) {
					return;
				}
				if (l >= L && r <= R) {
					int a = bsli(v, st[i], cv[q], cv[q](v[p]) + (q % 2 == 1));
					if (a >= 0 && (res == -1 || dv[q](v[pref[i][a]]) < dv[q](v[res]))) {
						res = pref[i][a];
					}
					return;
				}
				query(i * 2 + 1, l, (l + r) / 2);
				query(i * 2 + 2, (l + r) / 2 + 1, r);
			};
			query(0, 0, N - 1);
			if (res != -1) {
				g[p].push_back({res, dv[q](v[res]) - dv[q](v[p])});
				g[res].push_back({p, dv[q](v[res]) - dv[q](v[p])});
			}
		}
	}
	cout << prim(g, 0) << '\n';
	return 0;
}