// includes {{{
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
#include<map>
#include<set>
#include<tuple>
#include<cmath>
#include<random>
#include<cassert>
// }}}
// #include<bits/stdc++.h>
using namespace std;
using ll = long long;

ll n, d;
const int N = 1e5;
int r[N + 1];
int c[1000][1000];
int s[1000][1000];
int t1[1000][1000];
int t2[1000][1000];

// range2D accum2D {{{
template < class T >
ll range2D(T &val, int y1, int x1, int y2, int x2, int h, int w) {
  if(y1 < 0) y1 = 0;
  if(x1 < 0) x1 = 0;
  if(y2 >= h) y2 = h - 1;
  if(x2 >= w) x2 = w - 1;
  if(y1 > y2 || x1 > x2) return ll(0);
  ll res(val[y2][x2]);
  if(y1 - 1 >= 0) res -= val[y1 - 1][x2];
  if(x1 - 1 >= 0) res -= val[y2][x1 - 1];
  if(y1 - 1 >= 0 && x1 - 1 >= 0) res += val[y1 - 1][x1 - 1];
  return res;
}

template < class T >
void accum2D(T &val, int h, int w) {
  for(int i = 1; i < h; i++)
    for(int j = 0; j < w; j++) val[i][j] += val[i - 1][j];
  for(int i = 0; i < h; i++)
    for(int j = 1; j < w; j++) val[i][j] += val[i][j - 1];
}

template < class T >
ll range2Dloop(T &val, ll ty1, ll tx1, ll y2, ll x2, int h, int w) {
  if(ty1 > y2 || tx1 > x2) return ll(0);

  ll y1 = ty1 % h;
  if(y1 < 0) y1 += h;
  ll x1 = tx1 % w;
  if(x1 < 0) x1 += w;

  y2 += y1 - ty1;
  x2 += x1 - tx1;

  ll gy = y2 / h;
  ll gx = x2 / w;
  y2 %= h;
  x2 %= w;

  ll res(0);
  if(gy == 0 && gx == 0) {
    res += range2D<T>(val, y1, x1, y2, x2, h, w);
  } else if(gy == 0) {
    res += range2D<T>(val, y1, x1, y2, w - 1, h, w);
    res += range2D<T>(val, y1, 0, y2, x2, h, w);
    res += range2D<T>(val, y1, 0, y2, w - 1, h, w) * (gx - 1);
  } else if(gx == 0) {
    res += range2D<T>(val, y1, x1, h - 1, x2, h, w);
    res += range2D<T>(val, 0, x1, y2, x2, h, w);
    res += range2D<T>(val, 0, x1, h - 1, x2, h, w) * (gy - 1);
  } else {
    res += range2D<T>(val, y1, x1, h - 1, w - 1, h, w); // UL
    res += range2D<T>(val, 0, x1, y2, w - 1, h, w); // DL
    res += range2D<T>(val, y1, 0, h - 1, x2, h, w); // UR
    res += range2D<T>(val, 0, 0, y2, x2, h, w); // DR
    res += range2D<T>(val, y1, 0, h - 1, w - 1, h, w) * (gx - 1); // U
    res += range2D<T>(val, 0, 0, y2, w - 1, h, w) * (gx - 1); // D
    res += range2D<T>(val, 0, x1, h - 1, w - 1, h, w) * (gy - 1); // L
    res += range2D<T>(val, 0, x1, h - 1, x2, h, w) * (gy - 1); // R
    res += range2D<T>(val, 0, 0, h - 1, w - 1, h, w) * (gy - 1) * (gx - 1); // C
  }
  return res;
}

// }}}

int m(int x, int y) {
  return (x % y + y) % y;
}

int main() {
  std::ios::sync_with_stdio(false), std::cin.tie(0);
  cin >> n >> d;
  for(int i = 0; i < n; i++) {
    int x, y; cin >> x >> y;
    c[m(x, d)][m(y, d)]++;
  }

  r[0] = 0;
  for(int i = 1; i <= N; i++) {
    r[i] = r[i - 1];
    if(r[i] * r[i] < i) r[i]++;
  }

  int ma = 0;
  int sum1 = 0, sum2 = 0;
  for(int i = 0; i < d; i++) for(int j = 0; j < d; j++) s[i][j] = r[c[i][j]], ma = max(ma, s[i][j]);
  for(int i = 0; i < d; i++) for(int j = 0; j < d; j++) {
    if(s[i][j] == ma) {
      if(s[i][j] * (s[i][j] - 1) >= c[i][j]) {
        t2[i][j]++;
        sum2++;
      } else {
        t1[i][j]++;
        sum1++;
      }
    }
  }

  accum2D(t1, d, d);
  accum2D(t2, d, d);

  // d * (ma - 1) + (1 to d)

  int ok = d, ng = 0;
  while(ok - ng > 1) {
    int mid = (ok + ng) >> 1;
    int f = 0;
    for(int i = 0; i < d; i++) for(int j = 0; j < d; j++) {
      if(range2Dloop(t1, i, j, i + mid - 1, j + mid - 1, d, d) == sum1 &&
        range2Dloop(t2, i + mid, j + mid, i + d - 1, j + d - 1, d, d) == 0) {
        f = 1;
        goto b;
      }
    }
b:
    if(f) ok = mid; else ng = mid;
  }

  cout << d * (ma - 1) + ok - 1 << endl;

  return 0;
}


Measured memory_bytes: 16256