#include<bits/stdc++.h>
using namespace std;
void rd(int &x){
  int k, m=0;
  x=0;
  for(;;){
    k = getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
void wt_L(int x){
  char f[10];
  int m=0, s=0;
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    putchar_unlocked('-');
  }
  while(s--){
    putchar_unlocked(f[s]+'0');
  }
}
template<class S, class T> inline S chmax(S &a, T b){
  if(a<b){
    a=b;
  }
  return a;
}
int D, N, mn[1000][1000], mx[1000][1000], p[1000][1000], t[1001][1001];
inline void ad(int x1, int x2, int y1, int y2, int v){
  if(x1 < 0){
    ad(x1+D, D-1, y1, y2, v);
    ad(0, x2, y1, y2, v);
    return;
  }
  if(y1 < 0){
    ad(x1, x2, y1+D, D-1, v);
    ad(x1, x2, 0, y2, v);
    return;
  }
  t[x2+1][y2+1]+=v;
  t[x1][y2+1]-=v;
  t[x2+1][y1]-=v;
  t[x1][y1]+=v;
}
int main(){
  int Lj4PdHRW, i, j, k, m, res, tot, x, y, z;
  rd(N);
  rd(D);
  for(Lj4PdHRW=0;Lj4PdHRW<N;Lj4PdHRW++){
    rd(i);
    rd(j);
    p[i%D][j%D]++;
  }
  for(i=0;i<D;i++){
    for(j=0;j<D;j++){
      k = p[i][j];
      if(k==0){
        mn[i][j] = mx[i][j] = 0;
        continue;
      }
      for(x=0;;x++){
        if(x*x >= k){
          break;
        }
      }
      if(x * (x-1) >= k){
        mn[i][j] = x-1;
        mx[i][j] = x;
      }
      else{
        mn[i][j] = mx[i][j] = x;
      }
    }
  }
  m = 0;
  for(i=0;i<D;i++){
    for(j=0;j<D;j++){
      chmax(m, mx[i][j]);
    }
  }
  for(i=0;i<D;i++){
    for(j=0;j<D;j++){
      p[i][j] = 0;
      if(mx[i][j] != m){
        continue;
      }
      if(mx[i][j] == mn[i][j]){
        p[i][j] = 2;
      }
      else{
        p[i][j] = 1;
      }
    }
  }
  x = 0;
  y = D-1;
  while(x < y){
    z = (x+y)/2;
    tot = 0;
    for(i=0;i<D+1;i++){
      for(j=0;j<D+1;j++){
        t[i][j] = 0;
      }
    }
    for(i=0;i<D;i++){
      for(j=0;j<D;j++){
        if(p[i][j] == 2){
          ad(i-z,i,j-z,j,1);
          tot++;
        }
        if(p[i][j] == 1){
          ad(0,D-1,j-z,j,1);
          ad(i-z,i,0,D-1,1);
          ad(i-z,i,j-z,j,-1);
          tot++;
        }
      }
    }
    k = 0;
    for(i=1;i<D+1;i++){
      t[i][0] += t[i-1][0];
    }
    for(i=1;i<D+1;i++){
      t[0][i] += t[0][i-1];
    }
    for(i=1;i<D+1;i++){
      for(j=1;j<D+1;j++){
        t[i][j] += t[i-1][j] + t[i][j-1] - t[i-1][j-1];
      }
    }
    for(i=0;i<D;i++){
      for(j=0;j<D;j++){
        if(t[i][j]==tot){
          k = 1;
        }
      }
    }
    if(k){
      y = z;
    }
    else{
      x = z+1;
    }
  }
  res = (m-1) * D + x;
  wt_L(res);
  putchar_unlocked('\n');
  return 0;
}
// cLay varsion 20180730-1

// --- original code ---
// int N, D;
// int p[1000][1000];
// int mn[1000][1000], mx[1000][1000];
// 
// int t[1001][1001];
// 
// inline void ad(int x1, int x2, int y1, int y2, int v){
//   if(x1 < 0){
//     ad(x1+D, D-1, y1, y2, v);
//     ad(0, x2, y1, y2, v);
//     return;
//   }
//   if(y1 < 0){
//     ad(x1, x2, y1+D, D-1, v);
//     ad(x1, x2, 0, y2, v);
//     return;
//   }
//   t[x2+1][y2+1]+=v;
//   t[x1][y2+1]-=v;
//   t[x2+1][y1]-=v;
//   t[x1][y1]+=v;
// }
// 
// {
//   int i, j, k, x, y, z, m, tot;
//   int res;
//   
//   rd(N,D);
//   rep(N){
//     rd(i,j);
//     p[i%D][j%D]++;
//   }
// 
//   rep(i,D) rep(j,D){
//     k = p[i][j];
//     if(k==0){
//       mn[i][j] = mx[i][j] = 0;
//       continue;
//     }
//     for(x=0;;x++) if(x*x >= k) break;
//     if(x * (x-1) >= k){
//       mn[i][j] = x-1;
//       mx[i][j] = x;
//     } else {
//       mn[i][j] = mx[i][j] = x;
//     }
//   }
// 
//   m = 0;
//   rep(i,D) rep(j,D) m >?= mx[i][j];
// 
//   rep(i,D) rep(j,D){
//     p[i][j] = 0;
//     if(mx[i][j] != m) continue;
//     if(mx[i][j] == mn[i][j]) p[i][j] = 2;
//     else                     p[i][j] = 1;
//   }
// 
// //  rep(i,D) wt(p[i](D));
// 
//   x = 0; y = D-1;
//   while(x < y){
//     z = (x+y)/2;
//     tot = 0;
// 
//     rep(i,D+1) rep(j,D+1) t[i][j] = 0;
// 
//     rep(i,D) rep(j,D){
//       if(p[i][j] == 2){
//         ad(i-z,i,j-z,j,1);
//         tot++;
//       }
//       if(p[i][j] == 1){
//         ad(0,D-1,j-z,j,1);
//         ad(i-z,i,0,D-1,1);
//         ad(i-z,i,j-z,j,-1);
//         tot++;
//       }
//     }
// 
//     k = 0;
//     rep(i,1,D+1) t[i][0] += t[i-1][0];
//     rep(i,1,D+1) t[0][i] += t[0][i-1];
//     rep(i,1,D+1) rep(j,1,D+1) t[i][j] += t[i-1][j] + t[i][j-1] - t[i-1][j-1];
//     
// //    wt(z);
// //    rep(i,D+1) wt(t[i](D+1));
//     
//     rep(i,D) rep(j,D) if(t[i][j]==tot) k = 1;
//     if(k) y = z; else x = z+1;
//   }
// 
//   res = (m-1) * D + x;
//   wt(res);
// }


Measured memory_bytes: 15872