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

int a[2010][2010];
int sum1[2010][2010], sum2[2010][2010];
int n, d, now;

int chmax(int &x, int y){
	x = x > y ? x : y;
}

int count1(int a, int b, int c, int d){
	if (a > c || b > d) return 0;
	return sum1[c][d] - sum1[a - 1][d] - sum1[c][b - 1] + sum1[a - 1][b - 1];
}

int count2(int a, int b, int c, int d){
	if (a > c || b > d) return 0;
	return sum2[c][d] - sum2[a - 1][d] - sum2[c][b - 1] + sum2[a - 1][b - 1];
}

int check(int k){
	for (int i = 1; i <= d; i++){
		for (int j = 1; j <= d; j++){
			int flag = 1;
			if (count1(i + k, j + k, d + i - 1, d + j - 1) != (d - k) * (d - k)) flag = 0;
			if (count2(1, 1, d, d) - count2(i, j, i + k - 1, j + k - 1) != d * d - k * k) flag = 0;
			if (flag) return 1;
		}
	}
	return 0;
}

int main(){
	scanf("%d%d", &n, &d);
	for (int i = 0; i < n; i++){
		int x, y; scanf("%d%d", &x, &y);
		a[x % d + 1][y % d + 1]++;
	}
	int maxj = 0;
	for (int i = 1; i <= d; i++){
		for (int j = 1; j <= d; j++){
			maxj = max(maxj, a[i][j]);
		}
	}
	now = 1;
	while (now * now < maxj) now++;
	now--;
	for (int i = 1; i <= 2 * d; i++){
		for (int j = 1; j <= 2 * d; j++){
			a[i][j] = a[(i - 1) % d + 1][(j - 1) % d + 1];
			sum1[i][j] = sum1[i - 1][j] + sum1[i][j - 1] - sum1[i - 1][j - 1] + (a[i][j] <= now * now);
			sum2[i][j] = sum2[i - 1][j] + sum2[i][j - 1] - sum2[i - 1][j - 1] + (a[i][j] <= now * (now + 1));
		}
	}
	int l = 0, r = d;
	while (l < r){
		int mid = l + r >> 1;
		if (check(mid)) r = mid;
		else l = mid + 1;
	}
	printf("%d\n", now * d - 1 + l);
	return 0;
}
