#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const ll linf = 1e18;
const double eps = 1e-12, pi = acos(-1);
template <typename Head>
void out(Head h) {
  cout << h << endl;
}
template <typename Head, typename... Tail>
void out(Head h, Tail... t) {
  cout << h << " ";
  out(t...);
}
template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
  for (auto&& x : v) is >> x;
  return is;
}
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  for (ll i = (0), __last_i = (v.size()); i < __last_i; i++) {
    if (i) os << " ";
    os << v[i];
  }
  return os;
}
template <typename T>
ostream& operator<<(ostream& os, const vector<string>& v) {
  for (ll i = (0), __last_i = (v.size()); i < __last_i; i++) {
    if (i) os << endl;
    os << v[i];
  }
  return os;
}
template <typename T>
ostream& operator<<(ostream& os, const vector<vector<T>>& v) {
  for (ll i = (0), __last_i = (v.size()); i < __last_i; i++) {
    if (i) os << endl;
    os << v[i];
  }
  return os;
}
struct yes_no : std::numpunct<char> {
  string_type do_truename() const { return "Yes"; }
  string_type do_falsename() const { return "No"; }
};
void solve();
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  locale loc(locale(), new yes_no);
  cout.imbue(loc);
  cout << fixed << setprecision(10) << boolalpha;
  solve();
}
void solve() {
  ll n, D;
  cin >> n >> D;
  vector<vector<ll>> sz(D, vector<ll>(D, 0));
  for (ll i = (0), __last_i = (n); i < __last_i; i++) {
    ll x, y;
    cin >> x >> y;
    sz[y % D][x % D]++;
  }
  vector<ll> szX(D, 0), szY(D, 0);
  vector<ll> minX(D, linf), minY(D, linf);
  for (ll y = (0), __last_y = (D); y < __last_y; y++)
    for (ll x = (0), __last_x = (D); x < __last_x; x++) {
      szX[x] += sz[y][x];
      szY[y] += sz[y][x];
      minX[x] = (minX[x] < sz[y][x] ? sz[y][x] : minX[x]);
      minY[y] = (minY[y] < sz[y][x] ? sz[y][x] : minY[y]);
    }
  auto check = [&](ll L) {
    vector<vector<ll>> sum(D, vector<ll>(D, 0));
    for (ll y = (0), __last_y = (D); y < __last_y; y++)
      for (ll x = (0), __last_x = (D); x < __last_x; x++) {
        sum[y][x] = ((L - y + D - 1) / D) * ((L - x + D - 1) / D);
      }
    vector<ll> sumX(D, 0), sumY(D, 0);
    vector<ll> maxX(D, 0), maxY(D, 0);
    for (ll y = (0), __last_y = (D); y < __last_y; y++)
      for (ll x = (0), __last_x = (D); x < __last_x; x++) {
        sumX[x] += sum[y][x];
        sumY[y] += sum[y][x];
        maxX[x] = (maxX[x] < sum[y][x] ? sum[y][x] : maxX[x]);
        maxY[y] = (maxY[y] < sum[y][x] ? sum[y][x] : maxY[y]);
      }
    vector<ll> X, Y;
    for (ll x = (0), __last_x = (D); x < __last_x; x++) {
      bool f = true;
      for (ll y = (0), __last_y = (D); y < __last_y; y++) {
        if (szY[y] > sumY[y] || maxY[y] < minY[y]) {
          f = false;
          break;
        }
      }
      X.push_back(x);
    }
    for (ll y = (0), __last_y = (D); y < __last_y; y++) {
      bool f = true;
      for (ll x = (0), __last_x = (D); x < __last_x; x++) {
        if (szX[x] > sumX[x] || maxX[x] < minX[x]) {
          f = false;
          break;
        }
      }
      Y.push_back(y);
    }
    for (auto&& bx : X)
      for (auto&& by : Y) {
        bool f = true;
        for (ll y = (0), __last_y = (D); y < __last_y; y++)
          for (ll x = (0), __last_x = (D); x < __last_x; x++) {
            if (sz[(by + y) % D][(bx + x) % D] > sum[y % D][x % D]) {
              f = false;
              break;
            }
          }
        if (f) {
          return true;
        }
      }
    return false;
  };
  ll lb = 0, ub = ll(1e9);
  for (ll t = (0), __last_t = (60); t < __last_t; t++) {
    ll mid = (lb + ub) / 2;
    if (check(mid))
      ub = mid;
    else
      lb = mid;
  }
  cout << ub - 1 << endl;
}
