#include <bits/stdc++.h>

using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;
#define rep(i, N) for(int i = 0; i < int(N); i++)
#define rep1(i, N) for (int i = 1; i <= int(N); i++)
#define fs first
#define sc second
#define pb push_back
#define PB push_back
#define MP make_pair
#define FOR(i, a, b) for (int i = int(a); i < int(b); i++)
#define REP(i, b) FOR(i, 0, b)

V<int> slide_max(const V<int>& v, int k) {
    V<int> idx; int st = 0;
    auto add = [&](int i) {
        while (st != int(idx.size()) && v[idx.back()] <= v[i]) idx.pop_back();
        idx.push_back(i);
    };

    int n = int(v.size());
    for (int i = 0; i < k-1; i++) {
        add(i);
    }
    V<int> res(n - k + 1);
    for (int i = 0; i <= n - k; i++) {
        add(i + (k-1));
        res[i] = v[idx[st]];
        if (idx[st] == i) st++;
    }
    return res;
}

int n;
int g[2010][2010];

VV<int> slide_max2d(int r, int c) {
    int h = n, w = n;

    static int hol[2010][2010];
    //VV<int> hol(w);
    for (int i = 0; i < w; i++) {
        V<int> buf(h);
        for (int j = 0; j < h; j++) {
            buf[j] = g[j][i];
        }
        auto res = slide_max(buf, r);
        for (int j = 0; j <= h - r; j++) {
            hol[i][j] = res[j];
        }
//        hol[i] = slide_max(buf, r);
    }
    VV<int> res(h - r + 1);
    for (int i = 0; i <= h - r; i++) {
        V<int> buf(w);
        for (int j = 0; j < w; j++) {
            buf[j] = hol[j][i];
        }
        res[i] = slide_max(buf, c);
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int m, d;
    cin >> m >> d;
    n = 2*d;

    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        g[x%d][y%d]++;
        g[x%d+d][y%d]++;
        g[x%d][y%d+d]++;
        g[x%d+d][y%d+d]++;
    }

    int ma = 0;
    for (int i = 0; i < d; i++) {
        for (int j = 0; j < d; j++) {
            ma = max(ma, g[i][j]);
        }
    }



/*    for (int i = 0; i < d; i++) {
        for (int j = 0; j < d; j++) {
            cout << g[i][j] << " ";
        }
        cout << endl;
    }*/
    ll lw = max(0LL, ll(sqrt(ma) - 1 + 1e-10) * d), up = ll(ceil(sqrt(ma) - 1e-10)) * d;
    while (up - lw > 1) {
        ll md = (lw + up) / 2;
        ll l = md / d;
        int rem = md % d;

        bool ok = false;
        auto big = slide_max2d(d - rem, d - rem);
        if (rem == 0) {
            for (int x = 0; x < d; x++) {
                for (int y = 0; y < d; y++) {
                    if (big[x][y] > l*l) continue;
                    ok = true;
                    break;
                }
                if (ok) break;
            }
        } else {
            auto small = slide_max2d(rem, rem);
            auto hbig = slide_max2d(d - rem, rem);
            auto wbig = slide_max2d(rem, d - rem);

            for (int x = 0; x < d; x++) {
                for (int y = 0; y < d; y++) {
                    if (big[x + rem][y + rem] > l * l) continue;
                    if (small[x][y] > l * l + l + l + 1) continue;
                    if (hbig[x + rem][y] > l * l + l) continue;
                    if (wbig[x][y + rem] > l * l + l) continue;
                    ok = true;
                    break;
                }
                if (ok) break;
            }
        }
        if (!ok) {
            lw = md;
        } else {
            up = md;
        }
    }
    cout << lw << endl;
    return 0;
}


Measured memory_bytes: 67232