#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <unordered_map>
using namespace std;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

template<class T> vector<T> make_vec(size_t a) { return vector<T>(a); }
template<class T, class... Ts> auto make_vec(size_t a, Ts... ts) {
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template<class T, class V>
typename enable_if<is_class<T>::value == 0>::type fill(T &t, const V &v) {
    t = v;
}
template<class T, class V>
typename enable_if<is_class<T>::value != 0>::type fill(T &t, const V &v){
    for (auto &e : t) fill(e, v);
}

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }

#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
template<class T> ostream& operator << (ostream &s, set<T> P)
{ EACH(it, P) { s << "<" << *it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }



int D;
int a[1010][1010];

// [x, y) に ..., i-D, i, i+D, i+2D, ... が何個あるか
// [x-i, y-i) に -D, 0, D, ... が何個あるか
long long num(long long x, long long y, long long i) {
    x -= i, y -= i;
    while (x <= 1) x += D, y += D;
    return (y-1) / D - (x-1) / D;
}

bool judge_tle(long long d) {
    for (int i = 0; i < D; ++i) {
        for (int j = 0; j < D; ++j) {

            bool ok = true;
            for (int i2 = 0; i2 < D; ++i2) {
                for (int j2 = 0; j2 < D; ++j2) {
                    long long need = a[i2][j2];
                    long long can = num(i, i + d+1, i2) * num(j, j + d+1, j2);

                    /*
                    COUT("-------------");
                    COUT(d); COUT(i); COUT(j);
                    cout << i2 << ", " << j2 << ": " << need << ", " << can << endl;
                    */
                    
                    if (can < need) ok = false;
                }
            }
            if (ok) return true;
        }
    }
    return false;
}


int dame[1010][1010];
bool judge(long long d) {
    //vector<vector<long long>> dame(D+1, vector<long long>(D+1, 0));
    memset(dame, 0, sizeof(dame));
    for (int x = 0; x < D; ++x) {
        for (int y = 0; y < D; ++y) {
            long long need = a[x][y];
            long long s = (long long)((long long)(sqrt(need)) + 0.5);
            if (s * s < need) ++s;
            --s;

            if (d < s * D) return false;
            if (d >= (s + 1) * D) continue;

            vector<long long> ax({0, 1, D-1, D}),
                ay({0, 1, D-1, D});

            for (int it = 0; it <= 1; ++it) {
                if (x + it >= 0 && x + it < D)
                    ax.push_back(x + it);
                if (y + it >= 0 && y + it < D)
                    ay.push_back(y + it);
            }
            
            {
                long long kox = x + D*s - d;
                for (int it = 0; it <= 1; ++it)
                    if (kox + it >= 0 && kox + it < D)
                        ax.push_back(kox+it);
                kox = x + D*(s+1) - d;
                for (int it = 0; it <= 1; ++it)
                    if (kox + it >= 0 && kox + it < D)
                        ax.push_back(kox+it);
            }
            {
                long long koy = y + D*s - d;
                for (int it = 0; it <= 1; ++it)
                    if (koy + it >= 0 && koy + it < D)
                        ay.push_back(koy+it);
                koy = y + D*(s+1) - d;
                for (int it = 0; it <= 1; ++it)
                    if (koy + it >= 0 && koy + it < D)
                        ay.push_back(koy+it);
            }

            sort(ax.begin(), ax.end());
            sort(ay.begin(), ay.end());
            ax.erase(unique(ax.begin(), ax.end()), ax.end());
            ay.erase(unique(ay.begin(), ay.end()), ay.end());

            /*
            COUT(ax);
            COUT(ay);
            */
            for (int i = 0; i+1 < ax.size(); ++i) {
                for (int j = 0; j+1 < ay.size(); ++j) {
                    long long can = num(ax[i], ax[i] + d+1, x) *
                        num(ay[j], ay[j] + d+1, y);
                    if (can < need) {
                        dame[ax[i]][ay[j]]++;
                        dame[ax[i+1]][ay[j]]--;
                        dame[ax[i]][ay[j+1]]--;
                        dame[ax[i+1]][ay[j+1]]++;
                    }
                }
            }
        }
    }

    for (int i = 0; i < D; ++i)
        for (int j = 0; j < D; ++j)
            dame[i+1][j] += dame[i][j];
    for (int i = 0; i < D; ++i)
        for (int j = 0; j < D; ++j)
            dame[i][j+1] += dame[i][j];
    for (int i = 0; i < D; ++i)
        for (int j = 0; j < D; ++j)
            if (dame[i][j] <= 0)
                return true;
    return false;
}

long long solve() {
    long long left = 0, right = 1LL<<20;
    while (right - left > 1) {
        long long x = (left + right) / 2;
        if (judge(x)) right = x;
        else left = x;
    }
    return right;
}

int main() {
    int N;
    while (cin >> N >> D) {
        memset(a, 0, sizeof(a));
        for (int i = 0; i < N; ++i) {
            int x, y;
            cin >> x >> y;
            a[x%D][y%D]++;
        }
        cout << solve() << endl;
    }
}
            












Measured memory_bytes: 8192