#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
const long long mod = 1000000007;
const long long inf = 1e18;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
long long powm(long long a, long long b, long long m);
pair<long long, long long> xy[100001];
long long fgrid[31][31], grid[31][31];
void solve() {
  long long n, d;
  cin >> n >> d;
  if (d > 30) exit(0);
  long long mmax = 0;
  for (long long i = 1; i <= n; i++) {
    cin >> xy[i].first >> xy[i].second;
    fgrid[xy[i].first % d][xy[i].second % d]++;
    mmax = max(mmax, fgrid[xy[i].first % d][xy[i].second % d]);
  }
  long long ans = inf;
  for (long long i = 0; i < d; i++)
    for (long long j = 0; j < d; j++) {
      if (!(mmax <= 10 || fgrid[i][j] > mmax / 3)) continue;
      for (long long k = 0; k < d; k++)
        for (long long l = 0; l < d; l++)
          grid[k][l] = fgrid[(k + i) % d][(l + j) % d];
      long long sum = n;
      long long grids = 0;
      while (sum > 0) {
        for (long long i = 0; i < grids; i++)
          if (grid[i % d][grids % d]) {
            sum--;
            grid[i % d][grids % d]--;
          }
        for (long long i = 0; i < grids; i++)
          if (grid[grids % d][i % d]) {
            sum--;
            grid[grids % d][i % d]--;
          }
        if (grid[grids % d][grids % d]) {
          grid[grids % d][grids % d]--;
          sum--;
        }
        grids++;
      }
      ans = min(ans, grids);
    }
  cout << ans - 1 << '\n';
}
signed main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  srand(chrono::steady_clock::now().time_since_epoch().count());
  long long t = 1;
  while (t--) solve();
  return 0;
}
long long powm(long long a, long long b, long long m) {
  long long te = 1;
  while (b) {
    if (b & 1) te = (te * a) % m;
    a = (a * a) % m;
    b >>= 1;
  }
  return te;
}
