There are n detachments on the surface, numbered from 1 to n, the i-th detachment is placed in a point with coordinates (x_i, y_i). All detachments are placed in different points.

Brimstone should visit each detachment at least once. You can choose the detachment where Brimstone starts.

To move from one detachment to another he should first choose one of four directions of movement (up, right, left or down) and then start moving with the constant speed of one unit interval in a second until he comes to a detachment. After he reaches an arbitrary detachment, he can repeat the same process.

Each t seconds an orbital strike covers the whole surface, so at that moment Brimstone should be in a point where some detachment is located. He can stay with any detachment as long as needed.

Brimstone is a good commander, that's why he can create at most one detachment and place it in any empty point with integer coordinates he wants before his trip. Keep in mind that Brimstone will need to visit this detachment, too.

Help Brimstone and find such minimal t that it is possible to check each detachment. If there is no such t report about it.

Input

The first line contains a single integer n (2 ≤ n ≤ 1000) — the number of detachments.

In each of the next n lines there is a pair of integers x_i, y_i (|x_i|, |y_i| ≤ 10^9) — the coordinates of i-th detachment.

It is guaranteed that all points are different.

Output

Output such minimal integer t that it is possible to check all the detachments adding at most one new detachment.

If there is no such t, print -1.

Examples

Input


4
100 0
0 100
-100 0
0 -100


Output


100

Input


7
0 2
1 0
-3 0
0 -2
-1 -1
-1 -3
-2 -3


Output


-1

Input


5
0 0
0 -1
3 0
-2 0
-2 1


Output


2

Input


5
0 0
2 0
0 -1
-2 0
-2 1


Output


2

Note

In the first test it is possible to place a detachment in (0, 0), so that it is possible to check all the detachments for t = 100. It can be proven that it is impossible to check all detachments for t < 100; thus the answer is 100.

In the second test, there is no such t that it is possible to check all detachments, even with adding at most one new detachment, so the answer is -1.

In the third test, it is possible to place a detachment in (1, 0), so that Brimstone can check all the detachments for t = 2. It can be proven that it is the minimal such t.

In the fourth test, there is no need to add any detachments, because the answer will not get better (t = 2). It can be proven that it is the minimal such t.
#include <bits/stdc++.h>
using namespace std;
template <class T = int>
using V = std::vector<T>;
template <class T = int>
using VV = std::vector<std::vector<T>>;
template <class T = int>
using VVV = std::vector<std::vector<std::vector<T>>>;
template <class T>
using pqup = std::priority_queue<T, std::vector<T>, std::greater<T>>;
using ll = long long;
using ld = long double;
using int128 = __int128_t;
using pii = std::pair<int, int>;
using pll = std::pair<long long, long long>;
template <class T, class U>
std::istream &operator>>(std::istream &is, std::pair<T, U> &p) {
  is >> p.first >> p.second;
  return is;
}
template <class T>
std::istream &operator>>(std::istream &is, std::vector<T> &v) {
  for (T &i : v) is >> i;
  return is;
}
std::istream &operator>>(std::istream &is, __int128_t &a) {
  std::string s;
  is >> s;
  __int128_t ret = 0;
  for (int i = 0; i < s.length(); i++)
    if ('0' <= s[i] and s[i] <= '9') ret = 10 * ret + s[i] - '0';
  a = ret * (s[0] == '-' ? -1 : 1);
  return is;
}
namespace scanner {
void scan(int &a) { std::cin >> a; }
void scan(long long &a) { std::cin >> a; }
void scan(std::string &a) { std::cin >> a; }
void scan(char &a) { std::cin >> a; }
void scan(char a[]) { std::scanf("%s", a); }
void scan(double &a) { std::cin >> a; }
void scan(long double &a) { std::cin >> a; }
template <class T, class U>
void scan(std::pair<T, U> &p) {
  std::cin >> p;
}
template <class T>
void scan(std::vector<T> &a) {
  std::cin >> a;
}
void INPUT() {}
template <class Head, class... Tail>
void INPUT(Head &head, Tail &...tail) {
  scan(head);
  INPUT(tail...);
}
}  // namespace scanner
template <class T, class U>
std::ostream &operator<<(std::ostream &os, const std::pair<T, U> &p) {
  os << p.first << " " << p.second;
  return os;
}
template <class T>
std::ostream &operator<<(std::ostream &os, const std::vector<T> &a) {
  for (int i = 0; i < int(a.size()); ++i) {
    if (i) os << " ";
    os << a[i];
  }
  return os;
}
std::ostream &operator<<(std::ostream &dest, __int128_t &value) {
  std::ostream::sentry s(dest);
  if (s) {
    __uint128_t tmp = value < 0 ? -value : value;
    char buffer[128];
    char *d = std::end(buffer);
    do {
      --d;
      *d = "0123456789"[tmp % 10];
      tmp /= 10;
    } while (tmp != 0);
    if (value < 0) {
      --d;
      *d = '-';
    }
    int len = std::end(buffer) - d;
    if (dest.rdbuf()->sputn(d, len) != len) {
      dest.setstate(std::ios_base::badbit);
    }
  }
  return dest;
}
template <class T>
void print(const T a) {
  std::cout << a << '\n';
}
template <class Head, class... Tail>
void print(Head H, Tail... T) {
  std::cout << H << ' ';
  print(T...);
}
template <class T>
void printel(const T a) {
  std::cout << a << '\n';
}
template <class T>
void printel(const std::vector<T> &a) {
  for (const auto &v : a) std::cout << v << '\n';
}
template <class Head, class... Tail>
void printel(Head H, Tail... T) {
  std::cout << H << '\n';
  printel(T...);
}
void Yes(const bool b = true) { std::cout << (b ? "Yes\n" : "No\n"); }
void No() { std::cout << "No\n"; }
void YES(const bool b = true) { std::cout << (b ? "YES\n" : "NO\n"); }
void NO() { std::cout << "No\n"; }
void err(const bool b = true) {
  if (b) {
    std::cout << "-1\n", exit(0);
  }
}
namespace debugger {
template <class T>
void view(const std::vector<T> &a) {
  std::cerr << "{ ";
  for (const auto &v : a) {
    std::cerr << v << ", ";
  }
  std::cerr << "\b\b }";
}
template <class T>
void view(const std::vector<std::vector<T>> &a) {
  std::cerr << "{\n";
  for (const auto &v : a) {
    std::cerr << "\t";
    view(v);
    std::cerr << "\n";
  }
  std::cerr << "}";
}
template <class T, class U>
void view(const std::vector<std::pair<T, U>> &a) {
  std::cerr << "{\n";
  for (const auto &p : a)
    std::cerr << "\t(" << p.first << ", " << p.second << ")\n";
  std::cerr << "}";
}
template <class T, class U>
void view(const std::map<T, U> &m) {
  std::cerr << "{\n";
  for (const auto &p : m)
    std::cerr << "\t[" << p.first << "] : " << p.second << "\n";
  std::cerr << "}";
}
template <class T, class U>
void view(const std::pair<T, U> &p) {
  std::cerr << "(" << p.first << ", " << p.second << ")";
}
template <class T>
void view(const std::set<T> &s) {
  std::cerr << "{ ";
  for (auto &v : s) {
    view(v);
    std::cerr << ", ";
  }
  std::cerr << "\b\b }";
}
template <class T>
void view(const T &e) {
  std::cerr << e;
}
}  // namespace debugger
template <class T>
int lb(const std::vector<T> &a, const T x) {
  return std::distance((a).begin(),
                       std::lower_bound((a).begin(), (a).end(), (x)));
}
template <class T>
int ub(const std::vector<T> &a, const T x) {
  return std::distance((a).begin(),
                       std::upper_bound((a).begin(), (a).end(), (x)));
}
template <class T>
void UNIQUE(std::vector<T> &a) {
  std::sort(a.begin(), a.end());
  a.erase(std::unique(a.begin(), a.end()), a.end());
}
template <class T>
std::vector<T> press(std::vector<T> &a) {
  auto res = a;
  UNIQUE(res);
  for (auto &v : a) v = lb(res, v);
  return res;
}
template <class T>
void ADD(std::vector<T> &a, const T x) {
  for (auto &v : a) v += x;
}
template <class T>
void SUB(std::vector<T> &a, const T x = 1) {
  for (auto &v : a) v -= x;
}
template <class T>
void MUL(std::vector<T> &a, const T x) {
  for (auto &v : a) v *= x;
}
template <class T>
void DIV(std::vector<T> &a, const T x) {
  for (auto &v : a) v /= x;
}
template <class T, class U>
inline bool chmin(T &a, const U &b) {
  return a > b ? a = b, true : false;
}
template <class T, class U>
inline bool chmax(T &a, const U &b) {
  return a < b ? a = b, true : false;
}
template <class T>
T divup(T x, T y) {
  return (x + y - 1) / y;
}
template <class T>
T POW(T a, long long n) {
  T ret = 1;
  while (n) {
    if (n & 1) ret *= a;
    a *= a;
    n >>= 1;
  }
  return ret;
}
long long POW(long long a, long long n, const int mod) {
  long long ret = 1;
  while (n) {
    if (n & 1) (ret *= a) %= mod;
    (a *= a) %= mod;
    n >>= 1;
  }
  return ret;
}
struct fast_io {
  fast_io() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
  }
} fast_io_;
const int inf = 1e9;
const ll INF = 2e9 + 5;
using R = long double;
constexpr R EPS = 1E-11;
int sgn(const R &r) { return (r > EPS) - (r < -EPS); }
int sgn(const R &a, const R &b) { return sgn(a - b); }
long long x10(const string &s, size_t n) {
  if (s.front() == '-') return -x10(s.substr(1), n);
  auto pos = s.find('.');
  if (pos == string::npos) return stoll(s + string(n, '0'));
  return stoll(s.substr(0, pos) + s.substr(pos + 1) +
               string(n + pos + 1 - s.size(), '0'));
}
long long ceildiv(long long a, long long b) {
  if (b < 0) a = -a, b = -b;
  if (a >= 0)
    return (a + b - 1) / b;
  else
    return a / b;
}
long long floordiv(long long a, long long b) {
  if (b < 0) a = -a, b = -b;
  if (a >= 0)
    return a / b;
  else
    return (a - b + 1) / b;
}
long long floorsqrt(long long x) {
  assert(x >= 0);
  long long ok = 0;
  long long ng = 1;
  while (ng * ng <= x) ng <<= 1;
  while (ng - ok > 1) {
    long long mid = (ng + ok) >> 1;
    if (mid * mid <= x)
      ok = mid;
    else
      ng = mid;
  }
  return ok;
}
inline int topbit(unsigned long long x) {
  return x ? 63 - __builtin_clzll(x) : -1;
}
inline int popcount(unsigned long long x) { return __builtin_popcountll(x); }
inline int parity(unsigned long long x) { return __builtin_parity(x); }
class DisjointSet {
 public:
  vector<ll> rank, p, sz;
  DisjointSet() {}
  DisjointSet(ll size) {
    rank.resize(size, 0);
    p.resize(size, 0);
    sz.resize(size, 1);
    for (int i = 0; i < (size); ++i) makeSet(i);
  }
  void makeSet(ll x) {
    p[x] = x;
    rank[x] = 0;
  }
  bool same(ll x, ll y) { return findSet(x) == findSet(y); }
  void unite(ll x, ll y) { link(findSet(x), findSet(y)); }
  void link(ll x, ll y) {
    if (rank[x] > rank[y]) {
      p[y] = x;
    } else {
      p[x] = y;
      if (rank[x] == rank[y]) {
        rank[y]++;
      }
    }
    sz[x] += sz[y];
    sz[y] = sz[x];
  }
  ll findSet(ll x) {
    if (x != p[x]) {
      p[x] = findSet(p[x]);
    }
    return p[x];
  }
};
void main_() {
  long long N;
  scanner::INPUT(N);
  V<ll> x(N), y(N);
  V<ll> xx(N), yy(N);
  map<ll, ll> pos_x, pos_y;
  for (int i = 0; i < (N); ++i) {
    cin >> x[i] >> y[i];
    pos_x[x[i]] = 1;
    pos_y[y[i]] = 1;
  }
  ll ind = 0;
  VV<ll> sx(N), sy(N);
  for (auto [x, y] : pos_x) {
    pos_x[x] = ind;
    ind++;
  }
  ind = 0;
  for (auto [x, y] : pos_y) {
    pos_y[x] = ind;
    ind++;
  }
  map<pll, ll> pos;
  for (int i = 0; i < (N); ++i) {
    ll nx = pos_x[x[i]];
    ll ny = pos_y[y[i]];
    sx[nx].push_back(ny);
    sy[ny].push_back(nx);
    pos[{nx, ny}] = i;
    xx[i] = nx;
    yy[i] = ny;
  }
  for (int i = 0; i < (N); ++i) {
    sort((sx[i]).begin(), (sx[i]).end());
    sort((sy[i]).begin(), (sy[i]).end());
  }
  VV<ll> sur(N), four(N, V<ll>(4, -1));
  for (int i = 0; i < (N); ++i) {
    ll nx = pos_x[x[i]];
    ll ny = pos_y[y[i]];
    ll itx = lower_bound(sx[nx].begin(), sx[nx].end(), ny) - sx[nx].begin();
    if (itx != 0) {
      ll dy = sx[nx][itx - 1];
      ll num = pos[{nx, dy}];
      sur[i].push_back(num);
      four[i][0] = num;
    }
    if (itx != ((int)(sx[nx]).size()) - 1) {
      ll uy = sx[nx][itx + 1];
      ll num = pos[{nx, uy}];
      sur[i].push_back(num);
      four[i][1] = num;
    }
    ll ity = lower_bound(sy[ny].begin(), sy[ny].end(), nx) - sy[ny].begin();
    if (ity != 0) {
      ll lx = sy[ny][ity - 1];
      ll num = pos[{lx, ny}];
      sur[i].push_back(num);
      four[i][2] = num;
    }
    if (ity != ((int)(sy[ny]).size()) - 1) {
      ll rx = sy[ny][ity + 1];
      ll num = pos[{rx, ny}];
      sur[i].push_back(num);
      four[i][3] = num;
    }
  }
  ll le = 0, ri = INF;
  while (ri - le > 1) {
    bool ok = false;
    ll t = (ri + le) / 2;
    DisjointSet ds = DisjointSet(N);
    for (int i = 0; i < (N); ++i) {
      for (auto p : sur[i]) {
        ll d = abs(x[i] - x[p]) + abs(y[i] - y[p]);
        if (d <= t && !ds.same(i, p)) {
          ds.unite(i, p);
        }
      }
    }
    if (ds.sz[ds.findSet(0)] == N) {
      ri = t;
      continue;
    }
    V<ll> par(N);
    set<ll> cnt;
    for (int i = 0; i < (N); ++i) {
      par[i] = ds.findSet(i);
      cnt.insert(par[i]);
    }
    for (int i = 0; i < (N); ++i) {
      if (ok) break;
      for (int j = 0; j < (N); ++j) {
        if (ok) break;
        ll si = ds.sz[par[i]];
        ll sj = ds.sz[par[j]];
        if (ds.same(i, j)) continue;
        if (x[i] == x[j]) {
          if (abs(y[i] - y[j]) <= 2 * t && si + sj == N) {
            ok = true;
            break;
          }
        }
        if (y[i] == y[j]) {
          if (abs(x[i] - x[j]) <= 2 * t && si + sj == N) {
            ok = true;
            break;
          }
        }
        ll ax = x[i], ay = y[j];
        if (abs(x[i] - x[j]) > t || abs(y[i] - y[j]) > t) continue;
        ll ar[4];
        ll z = 0;
        ar[z] = par[i];
        z++;
        ar[z] = par[j];
        z++;
        ll nx = xx[i];
        ll ny = yy[j];
        if (ax > x[j]) {
          if (four[j][3] != -1 && abs(ax - x[four[j][3]]) <= t) {
            ar[z] = par[four[j][3]];
            z++;
          }
        } else {
          if (four[j][2] != -1 && abs(ax - x[four[j][2]]) <= t) {
            ar[z] = par[four[j][2]];
            z++;
          }
        }
        if (ay > y[i]) {
          if (four[i][1] != -1 && abs(ay - y[four[i][1]]) <= t) {
            ar[z] = par[four[i][1]];
            z++;
          }
        } else {
          if (four[i][0] != -1 && abs(ay - y[four[i][0]]) <= t) {
            ar[z] = par[four[i][0]];
            z++;
          }
        }
        ll sum = 0;
        sort(ar, ar + z);
        for (int k = 0; k < (z); ++k) {
          if (k == 0)
            sum += ds.sz[ar[k]];
          else {
            if (ar[k] != ar[k - 1]) {
              sum += ds.sz[ar[k]];
            }
          }
        }
        if (sum == N) ok = true;
      }
    }
    if (ok)
      ri = t;
    else
      le = t;
  }
  if (ri == INF)
    cout << -1 << endl;
  else
    cout << ri << endl;
}
int main() {
  int t = 1;
  while (t--) main_();
  return 0;
}
