#include<stdio.h>
FILE*fin=fopen("wanted.in","r");
FILE*fout=fopen("wanted.out","w");
#define maxn 201
#define max(a,b)((a)>(b)?(a):(b))
#define inf 2000000000
int x[maxn],y[maxn],d[maxn][maxn],rez[2][maxn][maxn],n;
void ord()
{
  int o=0,i;
  while(!o)
  {
    o=1;
    for(i=1;i<n;i++)
      if(x[i]>x[i+1])
      {
	o=0;
	x[i]^=x[i+1]^=x[i]^=x[i+1];
	y[i]^=y[i+1]^=y[i]^=y[i+1];
      }
  }
}
int main()
{
  int i,j,k,nr,v,rf;
  fscanf(fin,"%d",&n);
  for(i=1;i<=n;i++)
    fscanf(fin,"%d%d",&x[i],&y[i]);
  fclose(fin);
  ord();
  for(i=1;i<=n;i++)
    d[i][i]=0;
  for(i=1;i<=n;i++)
  {
    for(j=i+1;j<=n;j++)
    {
      d[i][j]=d[j][i]=x[j]-x[i]+y[j]+y[i];
    }
  }
  for(i=1;i<=n;i++)
  {
    rez[0][i][i]=0;
    rez[1][i][i]=0;
  }
  for(i=1;i<n;i++)
  {
    rez[0][i][i+1]=d[i][i+1];
    rez[1][i][i+1]=d[i][i+1];
  }
  for(nr=3;nr<=n;nr++)
  {
    for(i=1;i<=n-nr+1;i++)
    {
      j=i+nr-1;
      v=inf;
      for(k=i+1;k<=j;k++)
	if(d[i][k]+max(rez[0][k][j],rez[1][i+1][k])<v)
	  v=d[i][k]+max(rez[0][k][j],rez[1][i+1][k]);
      rez[0][i][j]=v;
      v=inf;
      for(k=i;k<j;k++)
	if(d[j][k]+max(rez[0][k][j-1],rez[1][i][k])<v)
	  v=d[j][k]+max(rez[0][k][j-1],rez[1][i][k]);
      rez[1][i][j]=v;
    }
  }
  rf=inf;
  for(i=1;i<=n;i++)
    if(max(x[i],-x[i])+y[i]+max(rez[0][i][n],rez[1][1][i])<rf)
      rf=max(x[i],-x[i])+y[i]+max(rez[0][i][n],rez[1][1][i]);
  fprintf(fout,"%d",rf);
  fclose(fout);
  return 0;
}