#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
using namespace std;
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)
typedef long long ll;
typedef pair<int,int> pint;
typedef pair<ll,int> pli;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

int cnt[1010][1010];

int get(vector<vector<int>> &v,int x1,int y1,int x2,int y2){
    return v[x2][y2]+v[x1][y1]-v[x2][y1]-v[x1][y2];
}

int main(){
    int n,d;
    cin>>n>>d;
    rep(i,n){
        int x,y;
        cin>>x>>y;
        cnt[x%d][y%d]++;
    }
    int ma=0;
    rep(i,d)rep(j,d){
        int k=1;
        int rt=sqrt(cnt[i][j]);
        if(rt*rt<cnt[i][j])++rt;
        ma=max(rt,ma);
    }

    vector<vector<int>> sum1(2*d+2,vector<int>(2*d+2)),sum2(2*d+2,vector<int>(2*d+2));
    int tot1=0,tot2=0;
    rep(i,d)rep(j,d){
        if(cnt[i][j]>ma*(ma-1)){
            ++sum1[i][j],
            ++sum1[i+d][j],
            ++sum1[i][j+d],
            ++sum1[i+d][j+d],
            ++tot1;
        }
        else if(cnt[i][j]>(ma-1)*(ma-1)){
            ++sum2[i][j],
            ++sum2[i+d][j],
            ++sum2[i][j+d],
            ++sum2[i+d][j+d],
            ++tot2;
        }
    }
    rep(i,2*d)rep(j,2*d){
        sum1[i+1][j]+=sum1[i][j];
        sum2[i+1][j]+=sum2[i][j];
    }
    rep(i,2*d)rep(j,2*d){
        sum1[i][j+1]+=sum1[i][j];
        sum2[i][j+1]+=sum2[i][j];
    }

    int ok=d,ng=-1,mid;
    while(ok-ng>1){
        mid=(ok+ng)/2;
        bool can=false;
        rep(i,d)rep(j,d){
            if(get(sum1,i,j,i+mid,j+mid)==tot1&&
            get(sum2,i+mid,j+mid,i+d,j+d)==0){
                can=true;
                break;
            }
        }
        if(can)ok=mid;
        else ng=mid;
    }

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