#include <bits/stdc++.h>
using namespace std;
constexpr long long int MOD = 1000000007;
constexpr double EPS = 1e-8;
int N, M, K, H, W, L, R;
class Segment_Tree {
  vector<int> v;
  vector<int> l;
  vector<int> r;
  int num;
  int ret;
  int Update(int place) {
    if (place >= v.size() / 2) {
      return v[place];
    }
    v[place] = max(Update(place * 2), Update(place * 2 + 1));
    return v[place];
  }
  void RMQ(int a, int b, int place) {
    if (l[place] >= a && r[place] <= b) {
      ret = max(ret, v[place]);
      return;
    }
    if (l[place] > b || r[place] < a) return;
    RMQ(a, b, place * 2);
    RMQ(a, b, place * 2 + 1);
    return;
  }

 public:
  void Left(int place) {
    if (place >= v.size() / 2) {
      l[place] = place - v.size() / 2;
      return;
    }
    Left(place * 2);
    Left(place * 2 + 1);
    l[place] = l[place * 2];
    return;
  }
  void Right(int place) {
    if (place >= v.size() / 2) {
      r[place] = place - v.size() / 2;
      return;
    }
    Right(place * 2);
    Right(place * 2 + 1);
    r[place] = r[place * 2 + 1];
    return;
  }
  Segment_Tree(int n) {
    n++;
    num = 1;
    while (num < n * 2) {
      num *= 2;
    }
    l.resize(num);
    r.resize(num);
    v.resize(num, -MOD);
    Left(1);
    Right(1);
  }
  void Insert(int place, long long int num, bool update) {
    place += v.size() / 2;
    v[place] = num;
    if (!update) return;
    place /= 2;
    while (place) {
      v[place] = max(v[place * 2], v[place * 2 + 1]);
      place /= 2;
    }
  }
  void TopDown() { Update(1); }
  int RMQ(int a, int b) {
    ret = INT_MIN;
    RMQ(a, b, 1);
    return ret;
  }
};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> N >> K;
  vector<vector<int>> v(K, vector<int>(K));
  for (int i = 0; i < N; i++) {
    cin >> W >> H;
    v[H % K][W % K]++;
  }
  vector<vector<int>> hbox(K);
  for (int i = 0; i < K; i++) {
    for (int j = 0; j < K; j++) {
      if (v[i][j]) hbox[i].push_back(j);
    }
  }
  L = -1, R = 1000000;
  int mx = 0;
  for (auto i : v)
    for (auto j : i) mx = max(mx, j);
  L = (sqrt(mx)) * K - 1;
  R = sqrt(mx) * K + K;
  Segment_Tree r(K);
  vector<int> num(K);
  vector<int> rr(K);
  while (R - L > 1) {
    int mid = (R + L) / 2;
    bool flag = false;
    for (int i = 0; i < K; i++) {
      num[i] = (mid - i + K) / K;
    }
    for (int l = 0; l < K; l++) {
      for (int i = 0; i < K; i++) {
        rr[i] = 0;
        for (auto j : hbox[i]) {
          if (!num[i]) {
            rr[i] = MOD;
            break;
          }
          rr[i] =
              max(rr[i], (v[i][j] - 1) / num[i] * K + j + ((j < l) ? K : 0));
        }
      }
      for (int i = 0; i < K; i++) {
        r.Insert(i, rr[i], false);
      }
      r.TopDown();
      if (r.RMQ(0, K - 1) - l <= mid) {
        flag = true;
        break;
      }
      for (int d = 0; d < K; d++) {
        num[d]--;
        int nx = (d + 1 + mid) % K;
        num[nx]++;
        int nr = 0;
        for (auto j : hbox[d]) {
          if (!num[d]) {
            nr = MOD;
            break;
          }
          nr = max(nr, (v[d][j] - 1) / num[d] * K + j + ((j < l) ? K : 0));
        }
        r.Insert(d, nr, true);
        nr = 0;
        for (auto j : hbox[nx]) {
          if (!num[nx]) {
            nr = MOD;
            break;
          }
          nr = max(nr, (v[nx][j] - 1) / num[nx] * K + j + ((j < l) ? K : 0));
        }
        r.Insert(nx, nr, true);
        if (r.RMQ(0, K - 1) - l <= mid) flag = true;
        if (flag) break;
      }
      if (flag) break;
    }
    if (flag) {
      R = mid;
    } else {
      L = mid;
    }
  }
  cout << R << endl;
}
