using System;
using System.Collections.Generic;

namespace JAG
{
    class Program
    {
        struct Ter
        {
            public int x, y;
            public Ter(int _x, int _y)
            {
                x = _x;
                y = _y;
            }
        }

        static int Rastrakanost(List<Ter> zauzeteOdPrvog, List<Ter> teritorije, int n, int igrac)
        {
            if (zauzeteOdPrvog == null)
            {
                zauzeteOdPrvog = new List<Ter>();
            }
            if (n == 0 || (n == 1 && igrac == 2))
            {
                int max = 0;
                for (int i = 0; i < zauzeteOdPrvog.Count-1; i++)
                {
                    for (int j = i+1; j < zauzeteOdPrvog.Count; j++)
                    {
                        int dist = 0;
                        int prvi = Math.Abs(zauzeteOdPrvog[i].x - zauzeteOdPrvog[j].x);
                        int drugi = Math.Abs(zauzeteOdPrvog[i].y - zauzeteOdPrvog[j].y);
                        if (prvi == 1 && drugi == 1)
                        {
                            dist = 1;
                        }
                        else
                        {
                            dist = prvi + drugi;
                        }
                        if (dist > max)
                            max = dist;
                    }
                }
                return max;
            }
            if (igrac == 1)
            {
                int min = Int32.MaxValue;
                List<Ter> temp = new List<Ter>(zauzeteOdPrvog);
                foreach (var item in teritorije)
                {
                    temp.Add(item);
                    int m = Rastrakanost(temp, teritorije, n - 1, 2);
                    if (m < min)
                        min = m;
                    temp.Remove(item);
                }
                return min;
            }
            else
            {
                int max = Int32.MinValue;
                List<Ter> temp = new List<Ter>(teritorije);
                foreach ( var ter in teritorije)
                {
                    temp.Remove(ter);
                    int m = Rastrakanost(zauzeteOdPrvog, temp, n - 1, 1);
                    if (m > max)
                        max = m;
                    temp.Add(ter);
                }
                return max;
            }
        }
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            List<Ter> teritorije = new List<Ter>();
            for (int i = 0; i < n-1; i++)
            {
                string[] s = Console.ReadLine().Split(' ');
                int x = int.Parse(s[0]); int y = int.Parse(s[1]);
                teritorije.Add(new Ter(x, y));
            }
            Console.WriteLine(Rastrakanost(null, teritorije, n, 1));
        }
    }
}