#include <bits/stdc++.h>
using namespace std;

#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int64 i = 0;i < (n);i++)
#define FOR(i, a, b) for(int64 i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-10;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}

const int64 mod = 1e9+7;

int64 minsq(int64 x){ // x個を正方形内に入れる最小の正方形9 -> 3, 10 -> 4
	int64 a = sqrt(x);
	if(a*a >= x) return a;
	return a+1;
}

int main(void){
	int32 N, D;
	cin >> N >> D;
	vector<int64> x(N), y(N);
	REP(i, N) cin >> x[i] >> y[i];
	vector<vector<int32>> cnt(3030, vector<int32>(3030, 0));
	vector<vector<int32>> ok1(3030, vector<int32>(3030, 0));
	vector<vector<int32>> ok2(3030, vector<int32>(3030, 0));
	int64 d = 0;
	REP(i, N){
		cnt[x[i]%D][y[i]%D]++;
		chmax(d, cnt[x[i]%D][y[i]%D]);
	}
	using T = tuple<int64, int64, int64>;
	vector<T> v;
	sort(all(v), greater<T>());
	d = minsq(d);
	REP(i, D){
		REP(j, D){
			REP(k, 3){
				REP(l, 3){
					if(cnt[i][j] > (d-1)*(d-1)) ok1[i+D*k][j+D*l]++;
					if(cnt[i][j] > d*(d-1)) ok2[i+D*k][j+D*l]++;
				}
			}
		}
	}
	REP(i, 3*D){
		REP(j, 3*D){
			ok1[i][j+1] += ok1[i][j];
			ok2[i][j+1] += ok2[i][j];
		}
	}
	REP(j, 3*D){
		REP(i, 3*D){
			ok1[i+1][j] += ok1[i][j];
			ok2[i+1][j] += ok2[i][j];
		}
	}
	auto sum1 = [&](int32 x1, int32 y1, int32 x2, int32 y2){
		int32 res = ok1[x2][y2];
		if(x1 > 0) res -= ok1[x1-1][y2];
		if(y1 > 0) res -= ok1[x2][y1-1];
		if(x1 > 0 && y1 > 0) res += ok1[x1-1][y1-1];
		return res;
	};
	auto sum2 = [&](int32 x1, int32 y1, int32 x2, int32 y2){
		int32 res = ok2[x2][y2];
		if(x1 > 0) res -= ok2[x1-1][y2];
		if(y1 > 0) res -= ok2[x2][y1-1];
		if(x1 > 0 && y1 > 0) res += ok2[x1-1][y1-1];
		return res;
	};
	int32 l = -1, r = D+1, m;

	auto ok = [&](int32 b){
		REP(x, D){
			REP(y, D){
				bool ok = 1;
//				cout << x << " " << y << " " << b << endl;
//				cout << sum1(x, y+b+1, x+b, y+D-1) << " " << sum1(x+b+1, y, x+D-1, y+b) << " " << sum2(x+b+1, y+b+1, x+D-1, y+D-1) << endl;
				if(sum1(x+b+1, y+b+1, x+D-1, y+D-1) > 0) ok = 0;
				if(sum2(x+b+1, y, x+D-1, y+b) > 0) ok = 0;
				if(sum2(x, y+b+1, x+b, y+D-1) > 0) ok = 0;
				if(ok) return 1;
			}
		}
		return 0;
	};

	while(r-l > 1){
		m = (l+r)/2;
		if(ok(m))
			r = m;
		else
			l = m;
	}
	cout << (d-1)*D+r << endl;
}
