#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
using ll = long long;
using namespace std;
template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }

template <typename UnaryPredicate>
int64_t binsearch(int64_t l, int64_t r, UnaryPredicate p) {
    assert (l <= r);
    -- l;
    while (r - l > 1) {
        int64_t m = l + (r - l) / 2;
        (p(m) ? r : l) = m;
    }
    return r;
}

template <typename T>
struct cumulative_sum_2d {
    int h, w;
    vector<vector<T> > acc;
    bool frozen;
    cumulative_sum_2d(int h_, int w_) :
            h(h_),
            w(w_),
            acc(h + 1, vector<T>(w + 1)),
            frozen(false) {
    }
    void add(int y, int x, T value) {
        assert (not frozen);
        assert (0 <= y and y < h);
        assert (0 <= x and x < w);
        acc[y + 1][x + 1] += value;
    }
    void freeze() {
        assert (not frozen);
        frozen = true;
        REP (y, h) {
            REP (x, w) {
                acc[y + 1][x + 1] += acc[y + 1][x];
                acc[y + 1][x] += acc[y][x];  // in the same loop for speed
            }
            acc[y + 1][w] += acc[y][w];
        }
    }
    T get(int ly, int lx, int ry, int rx) const {  // [l, r)
        assert (frozen);
        assert (0 <= ly and ly <= ry and ry <= h);
        assert (0 <= lx and lx <= rx and rx <= w);
        return acc[ry][rx] - acc[ry][lx] - acc[ly][rx] + acc[ly][lx];
    }
    /**
     * @note call get O((ry - ly) / h * (rx - lx) / w) times
     */
    T get_torus(int ly, int lx, int ry, int rx) const {
        T acc = 0;
        while (ly < 0) { ly += h; ry += h; }
        while (lx < 0) { lx += w; rx += w; }
        for (int bi = ly / h; bi <= (ry - 1) / h; ++ bi) {
            int ly1 = (bi == ly / h ? ly % h : 0);
            int ry1 = (bi == ry / h ? ry % h : h);
            for (int bj = lx / w; bj <= (rx - 1) / w; ++ bj) {
                int lx1 = (bj == lx / w ? lx % w : 0);
                int rx1 = (bj == rx / w ? rx % w : w);
                acc += get(ly1, lx1, ry1, rx1);
            }
        }
        return acc;
    }
};

int solve(int n, int d, vector<int> const & x, vector<int> const & y) {
    auto cnt = vectors(d, d, 0);
    REP (i, n) {
        cnt[y[i] % d][x[i] % d] += 1;
    }

    return binsearch(0, 1e9, [&](ll r) {
        r += 1;
        ll lo = (r / d) * (r / d);
        ll mid = (r / d) * (r / d + 1);
        ll high = (r / d + 1) * (r / d + 1);
        cumulative_sum_2d<ll> acc(d, d);
        REP (y, d) REP (x, d) {
            if (cnt[y][x] <= lo) {
                // nop
            } else if (cnt[y][x] <= mid) {
                acc.add(y, x, 1);
            } else if (cnt[y][x] <= high) {
                acc.add(y, x, d * d + 1);
            } else {
                return false;
            }
        }
        acc.freeze();
        REP (y, d) REP (x, d) {
            if (0     < acc.get_torus(y + r % d, x + r % d, y + d,     x + d    )) continue;
            if (d * d < acc.get_torus(y + r % d, x,         y + d,     x + r % d)) continue;
            if (d * d < acc.get_torus(y,         x + r % d, y + r % d, x + d    )) continue;
            //          acc.get_torus(y,         x,         y + r % d, x + r % d)
            return true;
        }
        return false;
    });
}

int main() {
    int n, d; cin >> n >> d;
    vector<int> x(n), y(n);
    REP (i, n) cin >> x[i] >> y[i];
    cout << solve(n, d, x, y) << endl;
    return 0;
}


Measured memory_bytes: 12896