#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void maximize(T &a, T b) {
  a = max(a, b);
}
template <typename T>
inline void minimize(T &a, T b) {
  a = min(a, b);
}
template <typename T>
inline bool middle(T a, T b, T c) {
  return b <= a && a <= c;
}
template <class T>
inline bool MX(T &l, const T &r) {
  return l < r ? l = r, 1 : 0;
}
template <class T>
inline bool MN(T &l, const T &r) {
  return l > r ? l = r, 1 : 0;
}
inline void outputVI(vector<long long> x) {
  for (long long i = (0LL); i < (long long)((long long(x.size()))); i++) {
    cout << ((i) ? (" ") : ("")) << x[i];
  }
  cout << ("") << endl;
}
const long long SIZE1 = 2 * 1e6 + 1000;
const long long SIZE2 = 2010;
const long long SIZE3 = 400;
const long long SIZE = SIZE2;
const long long MAPSIZE = 40;
const long long p = 7 + 1e9;
const double INF = 1e18;
const long double EPS = 1e-7;
long long N, M, K, X, L, Y, Q, D;
vector<long long> edges[SIZE];
long long vals[SIZE], maps2[SIZE2][SIZE2], answer = 0LL;
long long maps[SIZE2][SIZE2];
long long A[SIZE];
long long sum[SIZE];
long long maxim = 0;
long long x[SIZE], y[SIZE];
long long chance[SIZE][SIZE];
long long rounded[SIZE][SIZE];
bool able[SIZE][SIZE];
long long solve2(long long x, long long y) {
  long long maxim2 = 0;
  for (long long i = (0LL); i < (long long)(D); i++)
    for (long long j = (0LL); j < (long long)(D); j++) {
      maps[(i - x + D) % D][(j - y + D) % D] = maps2[i][j];
    }
  for (long long i = (0LL); i < (long long)(D); i++) {
    for (long long j = (0LL); j < (long long)(D); j++) {
    }
  }
  return maxim2;
}
long long solve() {
  cin >> N >> D;
  for (long long i = (0LL); i < (long long)(N); i++) {
    cin >> x[i] >> y[i];
    x[i] %= D;
    y[i] %= D;
    maps2[x[i]][y[i]]++;
  }
  for (long long i = (0LL); i < (long long)(D); i++) {
    for (long long j = (0LL); j < (long long)(D); j++) {
      MX(maxim, maps2[x[i]][y[i]]);
    }
  }
  for (long long i = (0LL); i < (long long)(D); i++)
    for (long long j = (0LL); j < (long long)(D); j++) {
      rounded[i][j] = ceil(sqrt(maps2[i][j]));
      chance[i][j] = ceil(sqrt(maps2[i][j] + rounded[i][j]));
      able[i][j] = rounded[i][j] == chance[i][j];
    }
  for (long long i = (0LL); i < (long long)(D); i++) {
    for (long long j = (0LL); j < (long long)(D); j++) {
      for (long long k = (0LL); k < (long long)(2); k++)
        for (long long l = (0LL); l < (long long)(2); l++) {
          rounded[i + k * D][j + l * D] = rounded[i][j];
          chance[i + k * D][j + l * D] = chance[i][j];
          able[i + k * D][j + l * D] = able[i][j];
        }
    }
  }
  long long minium = INF;
  for (long long i = (0LL); i < (long long)(D); i++) {
    for (long long j = (0LL); j < (long long)(D); j++) {
      MN(minium, solve2(i, j));
    }
  }
  cout << minium - D << endl;
  return 0;
}
signed main() {
  solve();
  cin >> N;
}
