#include <bits/stdc++.h>
using namespace std;

int N, D;
int num[1000][1000];
int rad1[1000][1000], rad2[1000][1000];

int imos[2001][2001];
bool check(int X){
    int d = X/D, r = X%D;
    memset(imos, 0, sizeof(imos));

    for(int i=0; i<D; i++){
        for(int j=0; j<D; j++){
            if(rad2[i][j] > d+1) return false;
            if(rad2[i][j] <= d){
                imos[i][j]++;
                imos[i][j+D]--;
                imos[i+D][j]--;
                imos[i+D][j+D]++;
                continue;
            }

            if(rad1[i][j] == d){
                imos[i][j]++;
                imos[i][j+D]--;
                imos[i+D][j]--;
                imos[i+r+1][j+r+1]--;
                imos[i+D][j+r+1]++;
                imos[i+r+1][j+D]++;
            }else{
                imos[i][j]++;
                imos[i][j+r+1]--;
                imos[i+r+1][j]--;
                imos[i+r+1][j+r+1]++;
            }
        }
    }

    for(int i=0; i<=2*D; i++){
        for(int j=1; j<=2*D; j++) imos[i][j] += imos[i][j-1];
    }
    for(int i=1; i<=2*D; i++){
        for(int j=0; j<=2*D; j++) imos[i][j] += imos[i-1][j];
    }
    for(int i=0; i<D; i++){
        for(int j=0; j<D; j++){
            if(imos[i][j] + imos[i][j+D] + imos[i+D][j] + imos[i+D][j+D] == D*D) return true;
        }
    }
    return false;
}

int main(){
    cin >> N >> D;
    for(int i=0; i<N; i++){
        int x, y;
        cin >> x >> y;
        num[x%D][y%D]++;
    }

    for(int i=0; i<D; i++){
        for(int j=0; j<D; j++){
            while(rad1[i][j] * (rad1[i][j]+1) < num[i][j]) rad1[i][j]++;
            while(rad2[i][j] * rad2[i][j] < num[i][j]) rad2[i][j]++;
        }
    }

    int ng = -1, ok = 1e9;
    while(ok-ng>1){
        int mid = (ok+ng)/2;
        (check(mid) ? ok : ng) = mid;
    }
    cout << ok << endl;
    return 0;
}