#include <iostream>

using namespace std;

int n, D;
int c[1001][1001];
int A[1001][1001][3];
int sum_A[2002][2002][3];

int count(int k, int x1, int y1, int x2, int y2) {
  return sum_A[x2][y2][k] - sum_A[x1 - 1][y2][k] - sum_A[x2][y1 - 1][k] + sum_A[x1 - 1][y1 - 1][k];
}

bool check(int b) {
  for (int oy = 1; oy <= D; oy++) {
    for (int ox = 1; ox <= D; ox++) {
      if (count(0, ox, oy, ox + b, oy + b)) continue;
      if (count(1, ox + b + 1, oy + b + 1, ox + D - 1, oy + D - 1)) continue;
      if (count(2, ox + b + 1, oy, ox + D-1, oy + b)) continue;
      if (count(2, ox, oy + b + 1, ox + b, oy + D - 1)) continue;
      return true;
    }
  }
  return false;
}

int main(void) {
  cin >> n >> D;
  int cnt_max = 0;
  for (int i = 0; i < n; i++) {
    int x, y;
    cin >> x >> y;
    c[x % D][y % D]++;
    cnt_max = max(c[x % D][y % D], cnt_max);
  }
  int a = 0;
  while (cnt_max > (a + 1) * (a + 1))
    a++;

  for (int j = 0; j < D; j++) {
    for (int i = 0; i < D; i++) {
      A[i][j][0] = c[i][j] > (a + 1) * (a + 1);
      A[i][j][1] = c[i][j] > a * a;
      A[i][j][2] = c[i][j] > a * (a + 1);
    }
  }

  for (int k = 0; k < 3; k++)
    for (int j = 1; j <= 2 * D; j++)
      for (int i = 1; i <= 2 * D; i++)
        sum_A[i][j][k] += sum_A[i][j-1][k] + sum_A[i-1][j][k] - sum_A[i-1][j-1][k] + A[(i-1) % D][(j-1) % D][k];

  int l = -1, r = D - 1;
  while (l + 1 < r) {
    int b = (l + r) / 2;
    if (check(b))
      r = b;
    else
      l = b;
  }
  cout << a * D + r << endl;

  return 0;
}
