#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

template<typename T>
struct cumsum2D{
    int n, m;
    vector<vector<T>> dat;

    cumsum2D(){}
    cumsum2D(vector<vector<T>> &x){
        n = x.size();
        m = x[0].size();
        dat.assign(n+1, vector<T>(m+1));
        REP(i,n) REP(j,m){
            dat[i+1][j+1] = dat[i+1][j] + dat[i][j+1] - dat[i][j] + x[i][j];
        }
    }

    // [0, x) * [0, y)
    T sum(int x, int y){
        return dat[x][y];
    }

    // [x0, x1) * [y0 * y1)
    T sum(int x0, int y0, int x1, int y1){
        return sum(x1, y1) - sum(x0, y1) - sum(x1, y0) + sum(x0, y0);
    }
};

int main() {
    int n, d;
    cin >> n >> d;
    VVI cnt(d, VI(d));
    REP(i,n){
        int x = in(), y = in();
        cnt[x % d][y % d]++;
    }

    int ma = 0;
    REP(i,d) REP(j,d) ma = max(ma, cnt[i][j]);

    int x = 0;
    while ((x + 1) * (x + 1) < ma) x++;

    int c = 0, c2 = 0;
    VVI f(2 * d, VI(2 * d));
    VVI g(2 * d, VI(2 * d));
    REP(i,d) REP(j,d) if (cnt[i][j] > x * (x + 1)) {
        f[i][j] = f[i + d][j] = f[i][j + d] = f[i + d][j + d] = 1;
        c++;
    }
    REP(i,d) REP(j,d) if (cnt[i][j] > x * x) {
        g[i][j] = g[i + d][j] = g[i][j + d] = g[i + d][j + d] = 1;
        c2++;
    }


    // REP(i,d){
    //     REP(j,d) cout << cnt[i][j];
    //     cout << endl;
    // }
    // REP(i,d){
    //     REP(j,d) cout << f[i][j];
    //     cout << endl;
    // }
    // cout << endl;
    // REP(i,d){
    //     REP(j,d) cout << g[i][j];
    //     cout << endl;
    // }
    // cout << endl;

    cumsum2D<int> s1(f), s2(g);

    int ok = d, ng = -1;
    while (ok - ng > 1){
        int m = (ok + ng) / 2;
        bool f = false;
        REP(i,d) REP(j,d){
            int tmp = s1.sum(i, j, i + m, j + m);
            int tmp2 = s2.sum(i, j, i + d, j + m) + s2.sum(i, j, i + m, j + d) - s2.sum(i, j, i + m, j + m);
            if (tmp == c && tmp2 == c2){
                f = true;
                break;
            }
        }
        if (f) ok = m;
        else ng = m;
    }

    int ans = d * x - 1;
    ans += ok;
    cout << ans << endl;

    return 0;
}
