// bzoj1941

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<cmath>

#define LL long long

#define inf 1<<30

#define Pi acos(-1.0)

#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);

using namespace std;

const int maxn=1000010,maxm=2;

int n,K,ans1,ans2,rt;

struct KDtree {

	int v[maxm],mn[maxm],mx[maxm],l,r;

	friend bool operator < (const KDtree a,const KDtree b) {

		return a.v[K]<b.v[K];

	}

}tr[maxn],S;

int dis(KDtree a,KDtree b) {

	int res=0;

	for (int i=0;i<=1;i++) res+=abs(a.v[i]-b.v[i]);

	return res;

}

int eva1(int k) {

	if (!k) return inf;

	int res=0;

	for (int i=0;i<=1;i++) res+=max(0,S.v[i]-tr[k].mx[i])+max(0,tr[k].mn[i]-S.v[i]);

	return res;

}

int eva2(int k) {

	if (!k) return 0;

	int res=0;

	for (int i=0;i<=1;i++) res+=max(tr[k].mx[i]-S.v[i],S.v[i]-tr[k].mn[i]);

	return res;

}

void update(int k) {

	if (tr[k].l)

		for (int i=0;i<=1;i++) {

			tr[k].mx[i]=max(tr[k].mx[i],tr[tr[k].l].mx[i]);

			tr[k].mn[i]=min(tr[k].mn[i],tr[tr[k].l].mn[i]);

		}

	if (tr[k].r)

		for (int i=0;i<=1;i++) {

			tr[k].mx[i]=max(tr[k].mx[i],tr[tr[k].r].mx[i]);

			tr[k].mn[i]=min(tr[k].mn[i],tr[tr[k].r].mn[i]);

		}

}

int build(int l,int r,int p) {

	K=p;

	int mid=(l+r)>>1;

	nth_element(tr+l,tr+mid,tr+r+1);

	for (int i=0;i<=1;i++) tr[mid].mn[i]=tr[mid].mx[i]=tr[mid].v[i];

	if (l<mid) tr[mid].l=build(l,mid-1,p^1);

	if (mid<r) tr[mid].r=build(mid+1,r,p^1);

	update(mid);

	return mid;

}

void query1(int k) {

	if (S.v[0]!=tr[k].v[0] || S.v[1]!=tr[k].v[1]) ans1=min(ans1,dis(S,tr[k]));

	int dl=eva1(tr[k].l),dr=eva1(tr[k].r);

	if (dl<dr) {

		if (dl<ans1) query1(tr[k].l);

		if (dr<ans1) query1(tr[k].r);

	}

	else {

		if (dr<ans1) query1(tr[k].r);

		if (dl<ans1) query1(tr[k].l);

	}

}

void query2(int k) {

	ans2=max(ans2,dis(S,tr[k]));

	int dl=eva2(tr[k].l),dr=eva2(tr[k].r);

	if (dl>dr) {

		if (dl>ans2) query2(tr[k].l);

		if (dr>ans2) query2(tr[k].r);

	}

	else {

		if (dr>ans2) query2(tr[k].r);

		if (dl>ans2) query2(tr[k].l);

	}

}

int main() {

	scanf("%d",&n);

	for (int i=1;i<=n;i++) scanf("%d%d",&tr[i].v[0],&tr[i].v[1]);

	rt=build(1,n,0);

	int ans=inf;

	for (int i=1;i<=n;i++) {

		S=tr[i];

		ans1=inf;query1(rt);   //最小

		ans2=0;query2(rt);   //最大

		ans=min(ans,ans2-ans1);

	}

	printf("%d",ans);

	return 0;

}