#include <algorithm>
#include <iostream>
#include <set>
#include <vector>

using namespace std;
using tp = long long int;
constexpr tp Hat_S = 1e6 + 1;

tp n, d;
vector<pair<tp, tp>> v;

bool check(tp x) {
  vector<pair<tp, tp>>::iterator l = v.begin(), r = v.begin();
  multiset<tp> RMQ;
  for (vector<pair<tp, tp>>::iterator it = v.begin(); it != v.end(); ++it) {
    vector<pair<tp, tp>>::iterator t =
        upper_bound(it, v.end(), pair<tp, tp>(it->first + x, 0));
    while (r != t) {
      RMQ.insert(r++->second);
    }
    while (l != it) {
      RMQ.erase(RMQ.find(l++->second));
    }
    if (*RMQ.rbegin() - *RMQ.begin() >= d) {
      return 0;
    }
  }
  return 1;
}

tp calc() {
  tp l = 1, r = Hat_S;
  while (l <= r) {
    tp mid = l + r >> 1;
    if (check(mid)) {
      l = mid + 1;
    } else {
      r = mid - 1;
    }
  }
  return --l == Hat_S ? -1 : l;
}

signed main() {
  scanf("%lld%lld", &n, &d);
  v = vector<pair<tp, tp>>(n);
  for (auto&& i : v) {
    scanf("%lld%lld", &i.first, &i.second);
  }
  stable_sort(v.begin(), v.end());
  cout << calc() << '\n';
  return EXIT_SUCCESS;
}

/*#################################################################
#.................................................................#
#............................This.Code.Was.Created.By.RBTree......#
#.............#......#...............Limiting-Factor..............#
#............#.#....#.#.................Soul-Code.................#
#.............########............................................#
#............#........#..##############################...........#
#...........#..V....V......#..#........................#..#...#...#
#............#........#....#..........###..###..........#..#.#.#..#
#............#..X##X..#..#............#....#.#...........#..#...#.#
#...........#...N##N...#..#...........###..###..........#.........#
#.......MOE..#..@.....#....#.#.#.#...................#.#..........#
#.............########.....#.#.#.##############.#.#..#.#..........#
#..........................#.#.#.#.............#.#.#.#.#..........#
#......#########...........#.#.#.#.................#.#.#..........#
#.....#.........#..........#.#.#.#.................#.#.#..........#
#.#.#.#G#R#A#S#S#.#.#......#.#.#.#.................#.#.#..........#
#.###################......#.#.#.#.................#.#.#..........#
#...........................#.#.#...................#.#...........#
#.................................................................#
#################################################################*/