#include<bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
const int M = 1000000007;

int main() {
    int n, d;
    cin >> n >> d;
    vector<vector<int>> cnt(d, vector<int>(d));
    for (int i = 0; i < n; ++i) {
        int x, y;
        cin >> x >> y;
        ++cnt[x % d][y % d];
    }
    vector<vector<int>> ma(d, vector<int>(d));
    vector<vector<int>> mi(d, vector<int>(d));
    for (int i = 0; i < d; ++i) {
        for (int j = 0; j < d; ++j) {
            int ng = -2, ok = 1000;
            while (ng < ok - 1) {
                int m = (ok + ng) / 2;
                if ((m + 1) * (m + 1) >= cnt[i][j]) {
                    ok = m;
                }
                else {
                    ng = m;
                }
            }
            ma[i][j] = ok;
            if ((ok + 1) * ok >= cnt[i][j]) {
                mi[i][j] = ok - 1;
            }
            else {
                mi[i][j] = ok;
            }
        }
    }
    vector<P> v;
    int mma = 0;
    for (int i = 0; i < d; ++i) {
        for (int j = 0; j < d; ++j) {
            mma = max(mma, ma[i][j]);
        }
    }
    vector<bool> vi(d, false), vj(d, false);
    for (int i = 0; i < d; ++i) {
        for (int j = 0; j < d; ++j) {
            if (mi[i][j] == mma) {
                vi[i] = true;
                vj[j] = true;
            }
            else if (ma[i][j] == mma) {
                v.push_back(P(i, j));
            }
        }
    }
    int ans = M;
    int mai = 0;
    for (int i = 0; i < d; ++i) {
        if (vi[i]) mai = i;
    }
    for (int i = 0; i < d; ++i) {
        int maj = 0;
        for (int j = 0; j < d; ++j) {
            if (vj[j]) maj = j;
        }
        for (int j = 0; j < d; ++j) {
            int maa = max(mai, maj) + mma * d;
            if (maa < ans) {
                for (auto& p : v) {
                    int k = p.first, l = p.second;
                    int ofsi = (i <= k ? k - i : k - i + d);
                    int ofsj = (j <= l ? l - j : l - j + d);
                    if (ofsi < ofsj) {
                        maa = max({ maa, ofsi + ma[k][l] * d, ofsj + mi[k][l] * d });
                    }
                    else {
                        maa = max({ maa, ofsi + mi[k][l] * d, ofsj + ma[k][l] * d });
                    }
                }
            }
            ans = min(ans, maa);

            maj = max(0, maj - 1);
            if (vj[j]) {
                maj = d - 1;
            }
        }
        mai = max(0, mai - 1);
        if (vi[i]) {
            mai = d - 1;
        }
    }
    cout << ans << "\n";
    return 0;
}
