#include <bits/stdc++.h>

using namespace std;

const int max_n = 100011, max_d = 1011, inf = 1000111222;

int n, d, x[max_n], y[max_n], cnt[max_d][max_d];
int f[2 * max_d][2 * max_d];
int f2[2 * max_d][2 * max_d], fx[2 * max_d], fy[2 * max_d];

void proc(int f[][2 * max_d]) {
    for (int i = 1; i < 2 * d; ++i) {
        f[0][i] += f[0][i - 1];
        f[i][0] += f[i - 1][0];
    }
    for (int i = 1; i < 2 * d; ++i) {
        for (int j = 1; j < 2 * d; ++j) {
            f[i][j] += f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1];
        }
    }
}

int get_sum(int f[][2 * max_d], int lx, int ly, int rx, int ry) {
    int res = f[rx][ry];
    if (lx) {
        res -= f[lx - 1][ry];
    }
    if (ly) {
        res -= f[rx][ly - 1];
    }
    if (lx && ly) {
        res += f[lx - 1][ly - 1];
    }
    return res;
}

int get_sum(int f[2 * max_d], int l, int r) {
    if (l == 0) {
        return f[r];
    }
    return f[r] - f[l - 1];
}


bool check(int len) {
    long long cnt2 = len / d;
    long long cnt1 = cnt2 + 1;
    long long cnt3 = cnt1 * cnt2;
    cnt2 *= cnt2;
    cnt1 *= cnt1;
    if (cnt2 >= n) {
        return true;
    }
    memset(f, 0, sizeof(f));
    memset(f2, 0, sizeof(f2));
    memset(fx, 0, sizeof(fx));
    memset(fy, 0, sizeof(fy));
    int bad = 0;
    for (int i = 0; i < d; ++i) {
        for (int j = 0; j < d; ++j) {
            if (cnt[i][j] > cnt1) {
                return false;
            }
            if (cnt[i][j] <= cnt2) {
                continue;
            }
            //cout << i << " " << j << ": " << cnt[i][j] << endl;
            if (cnt[i][j] <= cnt3) {
                f2[i][j] = 1;
                f2[i][j + d] = 1;
                f2[i + d][j] = 1;
                f2[i + d][j + d] = 1;
                ++fx[i];
                ++fx[i + d];
                ++fy[j];
                ++fy[j + d];
                ++bad;
            } else if (cnt[i][j] > cnt2) {
                f[i][j] = 1;
                f[i + d][j] = 1;
                f[i][j + d] = 1;
                f[i + d][j + d] = 1;
                //cout << i << " " << j << endl;
                ++bad;
            }
        }
    }
    proc(f);
    proc(f2);
    for (int i = 1; i < 2 * d; ++i) {
        fx[i] += fx[i - 1];
        fy[i] += fy[i - 1];
    }
    int x = len % d;
    for (int i = 0; i < d; ++i) {
        for (int j = 0; j < d; ++j) {
            int c = get_sum(f, i, j, i + x, j + x);
            c += get_sum(fx, i, i + x);
            c += get_sum(fy, j, j + x);
            c -= get_sum(f2, i, j, i + x, j + x);
            /*if (cnt[i][j]) {
                cout << i << " " << j << ": " << c << ", bad = " << bad << endl;
            }*/
            if (c == bad) {
                return true;
            }
        }
    }
    return false;
}

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    scanf("%d%d", &n, &d);
    for (int i = 0; i < n; ++i) {
        scanf("%d%d", &x[i], &y[i]);
        ++cnt[x[i] % d][y[i] % d];
    }
    /*for (int i = 0; i < d; ++i) {
        for (int j = 0; j < d; ++j) {
            if (cnt[i][j]) {
                cout << i << " " << j << ": " << cnt[i][j] << endl;
            }
        }
    }*/
    //cout << check(4) << endl;
    //return 0;
    int l = 0, r = inf;
    while (r - l > 1) {
        int mid = (l + r) / 2;
        if (check(mid)) {
            r = mid;
        } else {
            l = mid;
        }
    }
    printf("%d\n", r);
    return 0;
}


Measured memory_bytes: 36992