#include <bits/stdc++.h>

using namespace std;
using int64 = long long;

constexpr int DEBUG = 0;

template<typename T>
vector<vector<T>> MakeVector2D(int d1, int d2, T default_value) {
  return vector<vector<T>>(d1, vector<T>(d2, default_value));
}

template<class T> inline bool UpdateMin(T& a, T b) {
  if (a > b) { a = b; return 1; } return 0;
}

template<class T> inline bool UpdateMax(T& a, T b) {
  if (a < b) { a = b; return 1; } return 0;
}

template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
  int len = v.size();
  s << "[";
  for (int i = 0; i < len; i++) {
    if (i > 0) s << ", ";
    s << v[i];
  }
  s << "]";
  return s;
}

vector<vector<int>> CumulativeSum2D(vector<vector<int>>& input) {
  int d1 = input.size();
  int d2 = input[0].size();
  auto c_sum = MakeVector2D(d1 + 1, d2 + 1, 0);
  for (int i = 1; i <= d1; i++) {
    for (int j = 1; j <= d2; j++) {
      c_sum[i][j] = c_sum[i - 1][j] + c_sum[i][j - 1] - c_sum[i - 1][j - 1] + input[i - 1][j - 1];
    }
  }
  return c_sum;
}

// Returns a tuple of (l, u) s.t.
// - l is the minimum value s.t. is_upper_fn(l) is false.
// - r is the minimum value s.t. is_upper_fn(r) is true.
//
// Required:
// - is_upper_fn is a function s.t.
//   - There exists a constant c s.t. is_upper_fn(x) is true for x >= c and
//     is_upper_fn(x) is false for x < c.
// - is_upper_fn(min_value) is false.
// - is_upper_fn(max_value) is true.
//
// Verified: ABC144E
tuple<int64, int64> BinarySearch(function<bool(int64)> is_upper_fn, int64 l, int64 u) {
  while (u - l >= 2) {
    int64 m = (l + u) / 2;
    if (is_upper_fn(m)) u = m; else l = m;
  }
  return make_tuple(l, u);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  int n, d;
  cin >> n >> d;
  vector<int64> xs(n), ys(n);
  for (int i = 0; i < n; i++) {
    cin >> xs[i] >> ys[i];
  }

  vector<int> sqrt_ceils(1000001, 0);
  for (int k = 1; k <= 1000; k++) {
    for (int x = (k - 1) * (k - 1) + 1; x <= k * k; x++) {
      sqrt_ceils[x] = k;
    }
  }

  auto count_table = MakeVector2D(d, d, 0);
  for (int i = 0; i < n; i++) {
    count_table[ys[i] % d][xs[i] % d]++;
  }

  int max_k = 0;
  for (int y = 0; y < d; y++) {
    for (int x = 0; x < d; x++) {
      UpdateMax(max_k, sqrt_ceils[count_table[y][x]]);
    }
  }

  // flag_matrix_1[y][x]: Whether count[y][x] > max_k * (max_k - 1)
  // flag_matrix_2[y][x]: Whether count[y][x] > (max_k - 1) * (max_k - 1)
  auto flag_matrix_1 = MakeVector2D(2 * d, 2 * d, 0);
  auto flag_matrix_2 = MakeVector2D(2 * d, 2 * d, 0);
  for (int y = 0; y < 2 * d; y++) {
    for (int x = 0; x < 2 * d; x++) {
      if (count_table[y % d][x % d] > max_k * (max_k - 1)) {
        flag_matrix_1[y][x] = 1;
      }
      if (count_table[y % d][x % d] > (max_k - 1) * (max_k - 1)) {
        flag_matrix_2[y][x] = 1;
      }
    }
  }

  auto c_sum_1 = CumulativeSum2D(flag_matrix_1);
  auto c_sum_2 = CumulativeSum2D(flag_matrix_2);

  auto count_fn = [](const vector<vector<int>>& c_sum, int l1, int u1, int l2, int u2) {
    return c_sum[u1][u2] - c_sum[l1][u2] - c_sum[u1][l2] + c_sum[l1][l2];
  };

  int min_r = INT32_MAX;
  for (int base_y = 0; base_y < d; base_y++) {
    for (int base_x = 0; base_x < d; base_x++) {
      auto check_fn = [&](int a) -> bool {
        int f1_count =
            count_fn(c_sum_1, base_y, base_y + d, base_x, base_x + d)
            - count_fn(c_sum_1, base_y, base_y + a + 1, base_x, base_x + a + 1);
        int f2_count = count_fn(c_sum_2, base_y + a + 1, base_y + d, base_x + a + 1, base_x + d);
        return f1_count == 0 && f2_count == 0;
      };
      if (check_fn(0)) {
        min_r = 0;
      } else {
        int l = 0;
        int u = d - 1;
        tie(l, u) = BinarySearch(check_fn, l, u);
        UpdateMin(min_r, u);
      }
    }
  }
  cout << d * (max_k - 1) + min_r << endl;
}

Measured memory_bytes: 72576