#include <iostream>
#include <vector>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;

int D;
int a[1010][1010];

// [x, y) に ..., i-D, i, i+D, i+2D, ... が何個あるか
// [x-i, y-i) に -D, 0, D, ... が何個あるか
long long num(long long x, long long y, long long i) {
    x -= i, y -= i;
    while (x <= 1) x += D, y += D;
    return (y-1) / D - (x-1) / D;
}

int dame[1010][1010];
bool judge(long long d) {
    //vector<vector<long long>> dame(D+1, vector<long long>(D+1, 0));
    memset(dame, 0, sizeof(dame));
    for (int x = 0; x < D; ++x) {
        for (int y = 0; y < D; ++y) {
            long long need = a[x][y];
            long long s = (long long)((long long)(sqrt(need)) + 0.5);
            if (s * s < need) ++s;
            --s;

            if (d < s * D) return false;
            if (d >= (s + 1) * D) continue;

            vector<long long> ax({0, 1, D-1, D}),
                ay({0, 1, D-1, D});

            for (int it = 0; it <= 1; ++it) {
                if (x + it >= 0 && x + it < D)
                    ax.push_back(x + it);
                if (y + it >= 0 && y + it < D)
                    ay.push_back(y + it);
            }
            
            {
                long long kox = x + D*s - d;
                for (int it = 0; it <= 1; ++it)
                    if (kox + it >= 0 && kox + it < D)
                        ax.push_back(kox+it);
                kox = x + D*(s+1) - d;
                for (int it = 0; it <= 1; ++it)
                    if (kox + it >= 0 && kox + it < D)
                        ax.push_back(kox+it);
            }
            {
                long long koy = y + D*s - d;
                for (int it = 0; it <= 1; ++it)
                    if (koy + it >= 0 && koy + it < D)
                        ay.push_back(koy+it);
                koy = y + D*(s+1) - d;
                for (int it = 0; it <= 1; ++it)
                    if (koy + it >= 0 && koy + it < D)
                        ay.push_back(koy+it);
            }

            sort(ax.begin(), ax.end());
            sort(ay.begin(), ay.end());
            ax.erase(unique(ax.begin(), ax.end()), ax.end());
            ay.erase(unique(ay.begin(), ay.end()), ay.end());
            for (int i = 0; i+1 < ax.size(); ++i) {
                for (int j = 0; j+1 < ay.size(); ++j) {
                    long long can = num(ax[i], ax[i] + d+1, x) *
                        num(ay[j], ay[j] + d+1, y);
                    if (can < need) {
                        dame[ax[i]][ay[j]]++;
                        dame[ax[i+1]][ay[j]]--;
                        dame[ax[i]][ay[j+1]]--;
                        dame[ax[i+1]][ay[j+1]]++;
                    }
                }
            }
        }
    }

    for (int i = 0; i < D; ++i)
        for (int j = 0; j < D; ++j)
            dame[i+1][j] += dame[i][j];
    for (int i = 0; i < D; ++i)
        for (int j = 0; j < D; ++j)
            dame[i][j+1] += dame[i][j];
    for (int i = 0; i < D; ++i)
        for (int j = 0; j < D; ++j)
            if (dame[i][j] <= 0)
                return true;
    return false;
}

long long solve() {
    long long left = 0, right = 1LL<<20;
    while (right - left > 1) {
        long long x = (left + right) / 2;
        if (judge(x)) right = x;
        else left = x;
    }
    return right;
}

int main() {
    int N;
    while (cin >> N >> D) {
        memset(a, 0, sizeof(a));
        for (int i = 0; i < N; ++i) {
            int x, y;
            cin >> x >> y;
            a[x%D][y%D]++;
        }
        cout << solve() << endl;
    }
}


Measured memory_bytes: 8192