KDtree是个吼东西啊……
枚举每一个点，然后求出离他距离最远和最近的点的距离，更新答案
然而为什么感觉KDtree只是因为剪枝才能跑得动呢……
//minamoto
#include<bits/stdc++.h>
#define R register
#define inf 0x3f3f3f3f
#define fp(i,a,b) for(R int i=a,I=b+1;i<I;++i)
#define fd(i,a,b) for(R int i=a,I=b-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
using namespace std;
char buf[1<<21],*p1=buf,*p2=buf;
inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
int read(){
R int res,f=1;R char ch;
while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);
for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');
return res*f;
}
const int N=1e6+5,M=2;
int n,K,ans1,ans2,rt;
struct KD{
int v[M],mn[M],mx[M],l,r;
inline bool operator <(const KD &b)const{return v[K]<b.v[K];}
}tr[N],S;
int dis(KD a,KD b){
int res=0;
fp(i,0,1)res+=abs(a.v[i]-b.v[i]);
return res;
}
int ck1(int p){
if(!p)return inf;int res=0;
fp(i,0,1)res+=max(0,S.v[i]-tr[p].mx[i])+max(0,tr[p].mn[i]-S.v[i]);
return res;
}
int ck2(int p){
if(!p)return 0;int res=0;
fp(i,0,1)res+=max(tr[p].mx[i]-S.v[i],S.v[i]-tr[p].mn[i]);
return res;
}
void upd(int p){
int l=tr[p].l,r=tr[p].r;
fp(i,0,1){
tr[p].mn[i]=tr[p].mx[i]=tr[p].v[i];
if(l)cmin(tr[p].mn[i],tr[l].mn[i]),cmax(tr[p].mx[i],tr[l].mx[i]);
if(r)cmin(tr[p].mn[i],tr[r].mn[i]),cmax(tr[p].mx[i],tr[r].mx[i]);
}
}
int build(int l,int r,int k){
K=k;int mid=(l+r)>>1;nth_element(tr+l,tr+mid,tr+r+1);
if(l<mid)tr[mid].l=build(l,mid-1,k^1);
if(mid<r)tr[mid].r=build(mid+1,r,k^1);
upd(mid);return mid;
}
void query1(int p){
if(S.v[0]!=tr[p].v[0]||S.v[1]!=tr[p].v[1])cmin(ans1,dis(S,tr[p]));
int dl=ck1(tr[p].l),dr=ck1(tr[p].r);
if(dl<dr){
if(dl<ans1)query1(tr[p].l);
if(dr<ans1)query1(tr[p].r);
}else{
if(dr<ans1)query1(tr[p].r);
if(dl<ans1)query1(tr[p].l);
}
}
void query2(int p){
cmax(ans2,dis(S,tr[p]));int dl=ck2(tr[p].l),dr=ck2(tr[p].r);
if(dl>dr){
if(dl>ans2)query2(tr[p].l);
if(dr>ans2)query2(tr[p].r);
}else{
if(dr>ans2)query2(tr[p].r);
if(dl>ans2)query2(tr[p].l);
}
}
int main(){
// freopen("testdata.in","r",stdin);
n=read();fp(i,1,n)tr[i].v[0]=read(),tr[i].v[1]=read();
rt=build(1,n,0);int ans=inf;
fp(i,1,n){
S=tr[i];
ans1=inf,query1(rt);
ans2=0,query2(rt);
cmin(ans,ans2-ans1);
}printf("%d\n",ans);return 0;
}