/*

Bus (IOI 2002)
Copyright (C) 2003 Maurizio Sambati

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA


In generale, il diametro in un grafo è la distanza massima tra due vertici; la
distanza tra due vertici è definita come la lunghezza del cammino minimo che li
collega. Se il grafo è dotato di pesi sui lati, le distanze vengono calcolate
sommando i pesi.

In questo problema, viene creato un grafo a partire da un insieme di fermate
posto sul piano: vengono scelte due stazioni a e b, collegate da un lato pesato
come la loro distanza, e tutte le rimanenti fermate vengono collegate ad a o b,
anche queste tramite un lato pesato come la distanza da a o b, rispettivamente.

Il problema è di scegliere a e b in maniera che il diametro del grafo
risultante sia minimo.

Notate che, fissate le stazioni, la lunghezza del diametro può essere realizzata da:
- la distanza fra le due fermate più distanti dalla prima stazione;
- la distanza fra le due fermate più distanti dalla seconda stazione;
- la distanza fra la fermata più distante dalla prima stazione alla fermata più
distante dalla seconda.

Questa soluzione trova il diametro minimo in questo modo: inizialmente
colleghiamo tutte le fermate alla prima stazione. Quindi le ordiniamo in ordine
decrescente di distanza, calcoliamo il diametro e verifichiamo se migliora o
meno la soluzione finora trovata. Infine, per ogni fermata proviamo ad
attaccarla alla seconda stazione, ricalcoliamo il diametro, e ricontrolliamo se
la soluzione corrente è stata migliorata

Ripetendo questa operazione per tutte le possibili combinazioni di stazioni
troviamo il diametro minimo.
  
*/

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

const int MAXN = 500;
int N;
struct coord {
  int x, y;
};

coord stop[MAXN];
int adj[MAXN][MAXN];
int ord[MAXN][MAXN];

void leggi();
void risolvi();

int main()
{
  leggi();
  risolvi();
}

void leggi()
{
  cin >> N;
  for( int i = 0; i < N; ++i ) {
    cin >> stop[i].x >> stop[i].y;
    for( int j = 0; j <= i; ++j ) {
      int dist = abs( stop[i].x - stop[j].x ) + abs( stop[i].y - stop[j].y );
      adj[i][j] = dist;
      adj[j][i] = dist;

      // mantiene una lista ordinata per ogni nodo di tutti gli altri nodi
      // [probabilmente usare un heap sarebbe stata una scelta più saggia,
      // ma non è questa la parte critica del problema]

      int k = j;
      while( k && ( adj[i][ ord[i][k-1] ] < dist ) ) {
	ord[i][k] = ord[i][k-1];
	--k;
      }
      ord[i][k] = j;

      k = i;
      while( k && ( adj[j][ ord[j][k-1] ] < dist ) ) {
	ord[j][k] = ord[j][k-1];
	--k;
      }
      ord[j][k] = i;	     
    }    
  }
}

void risolvi()
{
  int Dsol = INT_MAX;

  for( int h1 = 0; h1 < N; ++h1 ) {
    int Dcurr = adj[h1][ ord[h1][0] ] + adj[h1][ ord[h1][1] ];
    Dsol = min( Dsol, Dcurr );

    for( int h2 = (h1 + 1); h2 < N; ++h2 ) {  

      int p1 = 1;  // ordine del punto più distante dal primo hub
      int h1p1 = ord[h1][p1]; // primo punto più distante dal primo hub
      int h1p2 = h1;          // secondo punto più distante dal secondo hub
      if( h1p1 == h2 ) {
	++p1;
	h1p1 = ord[h1][p1];
      }
      int h2p1 = ord[h1][0]; // primo punto più distante dal secondo hub
      int h2p2 = h2;         // secondo punto più distante dal secondo hub (inizialmente
                             // se stesso, quindi nessuno)
      
      int dh12 = adj[h1][h2]; // distanza fra i due hub
 
      // bisogna trovare la distanza h1dist1 + dh12 + h2dist1

      for( int p2 = (p1 + 1); p2 < N; ++p2 ) {
	// il secondo punto più distante dal primo punto non
	// deve essere il secondo hub
	h1p2 = ord[h1][p2];
	if( h1p2 == h2 ) {
	  continue;
	}

	// calcola il diametro del grafo e vede se migliora la soluzione attuale
	Dcurr = max( max( adj[h1][h1p1] + adj[h1][h1p2],
			     adj[h1][h1p1] + dh12 + adj[h2][h2p1] ),
			adj[h2][h2p1] + adj[h2][h2p2] );
	Dsol = min( Dsol, Dcurr );

	// stacca il nodo dal primo hub e lo passa al secondo
	int nh2p1, nh2p2; // i potenziali nuovi nodi più distanti dal secondo hub
	nh2p1 = h2p1;
	nh2p2 = h2p2;
	if( adj[h2][h2p2] < adj[h2][h1p1] ) {
	  nh2p2 = h1p1;
	  if( adj[h2][h2p1] < adj[h2][nh2p2] ) {
	    swap( nh2p1, nh2p2 );
	  }
	}
	p1 = p2;
	h1p1 = h1p2;
	
	h2p1 = nh2p1;
	h2p2 = nh2p2;
      }
      Dcurr = max( max( adj[h1][h1p1] + adj[h1][h1p2],
			adj[h1][h1p1] + dh12 + adj[h2][h2p1] ),
		   adj[h2][h2p1] + adj[h2][h2p2] );
      Dsol = min( Dsol, Dcurr );
    }
  }
  cout << Dsol << endl;
}