#include <bits/stdc++.h>
using namespace std;
const long long mod = (1e+9) + 7;
const long long INF = (long long)1000000007 * 1000000007;
const long double eps = 1e-4;
const long double pi = acos(-1.0);
int n;
long long d;
long long x[1 << 17], y[1 << 17];
long long c[1000][1000];
long long ly[1000] = {};
long long calc(long long i, long long mid) {
  long long y = 0;
  for (int j = 0; j < d; j++) {
    for (int k = 0; k < d; k++) {
      if (!c[j][k]) continue;
      long long s = j;
      if (j < i) s += d;
      long long g = d * ((mid + i) / d) + j;
      if (g > mid + i) g -= d;
      long long num = (g - s) / d + 1;
      if (s > g) {
        y = INF;
      } else {
        long long ad = (c[j][k] + num - 1) / num;
        ad = max((long long)0, ad - 1);
        ly[k] = max(ly[k], ad);
      }
    }
  }
  long long ma = 0;
  for (int j = 0; j < d; j++) {
    ma = max(ma, ly[j]);
  }
  vector<long long> v;
  for (int j = 0; j < d; j++) {
    if (ma == ly[j]) {
      v.push_back(j);
    }
  }
  long long cy = ma * d;
  long long rest = 0;
  int llen = v.size();
  if (llen >= 2) {
    rest = v[llen - 1] - v[0];
    for (int j = 1; j < llen; j++) {
      rest = min(rest, v[j - 1] + d - v[j]);
    }
  }
  y = max(y, rest + cy);
  return y;
}
int main() {
  cin >> n >> d;
  for (int i = 0; i < n; i++) {
    cin >> x[i] >> y[i];
    c[x[i] % d][y[i] % d]++;
  }
  long long out = INF;
  for (int i = 0; i < d; i++) {
    long long le = 0;
    long long ri = mod * 4;
    while (ri - le > 1) {
      fill(ly, ly + d, -1);
      long long mid = (ri + le) / 2;
      long long y = calc(i, mid);
      out = min(out, max(mid, y));
      if (y > mid) {
        le = mid;
      } else {
        ri = mid;
      }
    }
    out = min(out, max(le - 1, calc(i, le - 1)));
    out = min(out, max(le, calc(i, le)));
    out = min(out, max(calc(i, ri), ri));
    out = min(out, max(calc(i, ri + 1), ri + 1));
  }
  cout << out << endl;
  return 0;
}
