#include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<algorithm>

 #include<queue>

 #include<vector>

 #include<map>

 #include<set>

 #define ll long long

 #define inf 2139062143

 #define MAXN 500100

 #define MOD 998244353

 #define rep(i,s,t) for(register int i=(s),i##__end=(t);i<=i##__end;++i)

 #define dwn(i,s,t) for(register int i=(s),i##__end=(t);i>=i##__end;--i)

 #define ren(x) for(register int i=fst[x];i;i=nxt[i])

 #define pb(i,x) vec[i].push_back(x)

 #define pls(a,b) (a+b)%MOD

 #define mns(a,b) (a-b+MOD)%MOD

 #define mul(a,b) (1LL*(a)*(b))%MOD

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(!isdigit(ch)) {if(ch=='-') f=-;ch=getchar();}

     while(isdigit(ch)) {x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 int rt,n,Dim,ret1,ret2,ans;

 struct node{int mx[],mn[],d[],l,r;}tr[MAXN],g;

 bool operator < (const node a,const node b) {return a.d[Dim]<b.d[Dim];}

 struct kd_tree

 {

     void upd(int k)

     {

         node gl=tr[tr[k].l],gr=tr[tr[k].r];

         rep(i,,)

         {

             if(tr[k].l) tr[k].mn[i]=min(tr[k].mn[i],gl.mn[i]),tr[k].mx[i]=max(tr[k].mx[i],gl.mx[i]);

             if(tr[k].r) tr[k].mn[i]=min(tr[k].mn[i],gr.mn[i]),tr[k].mx[i]=max(tr[k].mx[i],gr.mx[i]);

         }

     }

     int build(int l,int r,int D)

     {

         int mid=l+r>>;Dim=D;nth_element(tr+l,tr+mid,tr+r+);

         rep(i,,) tr[mid].mn[i]=tr[mid].mx[i]=tr[mid].d[i];

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

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

         upd(mid);return mid;

     }

     int Get1(int k,int res=)

     {

         rep(i,,) res+=max(abs(g.d[i]-tr[k].mn[i]),abs(g.d[i]-tr[k].mx[i]));

         return res;

     }

     int Get2(int k,int res=)

     {

         rep(i,,) res+=max(,tr[k].mn[i]-g.d[i]);

         rep(i,,) res+=max(,g.d[i]-tr[k].mx[i]);return res;

     }

     int dis(int k,int res=) {rep(i,,) res+=abs(tr[k].d[i]-g.d[i]);return res;}

     void query(int k)

     {

         int dl1=,dr1=,dl2=inf,dr2=inf;

         ret1=max(ret1,dis(k));if(dis(k)) ret2=min(ret2,dis(k));

         if(tr[k].l) dl1=Get1(tr[k].l),dl2=Get2(tr[k].l);

         if(tr[k].r) dr1=Get1(tr[k].r),dr2=Get2(tr[k].r);

         if(dl1>dr1)

         {

             if(dl1>ret1)

             {

                 query(tr[k].l);

                 if(dr1>ret1||dr2<ret2) query(tr[k].r);

             }else

             {

                 if(dr2<ret2) query(tr[k].r);

                 if(dl2<ret2) query(tr[k].l);

             }

         }else

         {

             if(dr1>ret1)

             {

                 query(tr[k].r);

                 if(dl1>ret1||dl2<ret2) query(tr[k].l);

             }else

             {

                 if(dl2<ret2) query(tr[k].l);

                 if(dr2<ret2) query(tr[k].r);

             }

         }

     }

 }kd;

 int main()

 {

     n=read();rep(i,,n) tr[i].d[]=read(),tr[i].d[]=read();

     rt=kd.build(,n,),ans=inf;

     rep(i,,n)

     {

         g=tr[i],ret1=,ret2=inf;kd.query(rt);

         ans=min(ans,ret1-ret2);

     }

     printf("%d\n",ans);

 }