#include <bits/stdc++.h>
#define mk make_pair
using namespace std;
typedef long long ll;
const int N = 2e3 + 5;
const int mod = 1e9 + 7;
int n, d, cnt[N][N];
int x[N * 100], y[N * 100];
int type[N][N];
int sum[N][N][2];
inline int S(int x, int y, int z) {
	if (x < 0 || y < 0) return 0;
	return sum[x][y][z];
}
bool check(int k) {
	++k;
	int x = k / d;
	ll t1 = (x + 1) * (x + 1ll);
	ll t2 = (x + 1ll) * x;
	ll t3 = (ll)x * x;
	for (int i = 0; i < d; ++i) {
		for (int j = 0; j < d; ++j) {
			if (cnt[i][j] <= t3) {
				type[i][j] = 2;
			} else 
			if (cnt[i][j] <= t2) {
				type[i][j] = 0;
			} else 
			if (cnt[i][j] <= t1) {
				type[i][j] = 1;
			} else {
				return 0;
			}
			//cout << type[i][j] << ",";
		} //cout << endl;
	}
	for (int i = 0; i < 2 * d; ++i) {
		for (int j = 0; j < 2 * d; ++j) {
			for (int k = 0; k < 2; ++k) {
				sum[i][j][k] = 0;
				if (i) sum[i][j][k] += sum[i - 1][j][k];
				if (j) sum[i][j][k] += sum[i][j - 1][k];
				if (i && j) sum[i][j][k] -= sum[i - 1][j - 1][k];
				if (k == type[i % d][j % d]) sum[i][j][k]++;
			}
		}
	}
	int tmp, tmp1, tmp2, p = k % d;
	for (int i = 0; i < d; ++i) {
		for (int j = 0; j < d; ++j) {
			tmp = S(i + p - 1, j + p - 1, 1) - S(i + p - 1, j - 1, 1) - S(i - 1, j + p - 1, 1) + S(i - 1, j - 1, 1);
			//cout << i << " " << j << " " << tmp << endl;
			if (sum[d - 1][d - 1][1] != tmp) continue;
			tmp1 = S(d - 1, j + p - 1, 0) - S(d - 1, j - 1, 0);
			tmp2 = S(i + p - 1, d - 1, 0) - S(i - 1, d - 1, 0);
			tmp = S(i + p - 1, j + p - 1, 0) - S(i + p - 1, j - 1, 0) - S(i - 1, j + p - 1, 0) + S(i - 1, j - 1, 0);
			if (tmp1 + tmp2 - tmp != sum[d - 1][d - 1][0]) continue;
			return 1;
		}
	}
	return 0;
}
int main() {
	scanf("%d %d", &n, &d);
	for (int i = 1; i <= n; ++i) {
		scanf("%d %d", x + i, y + i);
		cnt[x[i] % d][y[i] % d]++;
	}
	//check(4);return 0;
	int l = 1, r = 1e6 + 5;
	while (l < r) {
		int mid = l + r >> 1;
		//cout << mid << endl;
		if (l + 1 == r) {
			if (check(l))
				--r;
			else
				++l;
			break;
		}
		if (check(mid))
			r = mid; 
		else 
			l = mid;
	}
	cout << l;
} 