#if 1
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <list>

auto& in = std::cin;
auto& out = std::cout;
#define all_range(C) std::begin(C), std::end(C)
const double PI = 3.141592653589793238462643383279502884197169399375105820974944;

int32_t N, D;

int32_t num[1000][1000];
int32_t square[1000][1000];
int32_t num_one[2100][2100];
int32_t num_error[2100][2100];


using INT_T = int32_t;
template<typename ARR>
inline void add_full(ARR& v1, ARR& v2)
{
	v1 += v2;
}
template<typename ARR, size_t N>
inline void add_full(ARR(&v1)[N], ARR(&v2)[N])
{
	auto iter1 = v1, iter2 = v2, iter1end = v1 + N;
	while (iter1 != iter1end) {
		add_full(*iter1++, *iter2++);
	}
}
//1-indexed累積和
template<size_t N>void CuSum(INT_T(&arr)[N])
{
	for (size_t i = 2; i < N; i++)
	{
		arr[i] += arr[i - 1];
	}
}
template<typename ARR, size_t N>void CuSum(ARR(&arr)[N])
{
	for (auto& arr2 : arr) {
		CuSum(arr2);
	}
	for (size_t i = 2; i < N; i++)
	{
		add_full(arr[i], arr[i - 1]);
	}
}
#if 0
template<size_t N, size_t M>void CuSum(INT_T(&arr)[N][M])
{
	for (auto& arr2 : arr) {
		CuSum(arr2);
	}

	for (size_t i = 2; i < N; i++)
	{
		add_full(arr[i], arr[i - 1]);
	}
}
template<size_t N, size_t M, size_t O>void CuSum(INT_T(&arr)[N][M][O])
{
	for (auto& arr2 : arr) {
		CuSum(arr2);
	}

	for (size_t i = 2; i < N; i++)
	{
		add_full(arr[i], arr[i - 1]);
	}
}
#endif
//1-indexed、(]区間
template<size_t N> INT_T get_sum(INT_T(&arr)[N], int x, int x2)
{
	return (arr[x2] - arr[x]);
}
//1-indexed、(]区間
template<size_t N, size_t M> INT_T get_sum(INT_T(&arr)[N][M], int x, int y, int x2, int y2)
{
	return (arr[y2][x2] - arr[y][x2] - arr[y2][x] + arr[y][x]);
}
//1-indexed、(]区間
template<size_t N, size_t M, size_t O> INT_T get_sum(INT_T(&arr)[N][M][O], int x, int y, int z, int x2, int y2, int z2)
{

	return arr(arr[z2][y2][x2] - arr[z][y2][x2] - arr[z2][y][x2] - arr[z2][y2][x] + arr[z2][y][x] + arr[z2][y][x] + arr[z][y][x2] - arr[z][y][x]);
}


int main()
{
	using std::get;
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);
	in.tie(nullptr);
	out.tie(nullptr);

	in >> N >> D;

	for (size_t i = 0; i < N; i++)
	{
		int x, y;
		in >> x >> y;
		x %= D;
		y %= D;
		num[x][y]++;
	}

	int32_t max_square = -1;
	std::vector<std::tuple<int, int, int>> max_list;
	for (int32_t i = 0; i < D; i++)
	{
		for (int32_t j = 0; j < D; j++)
		{
			auto s = (int32_t)std::sqrt(square[i][j]);
			while ((s*s) < num[i][j]) {
				++s;
			}
			square[i][j] = s;
			int min_size = ((s*(s-1)) >= num[i][j])?1:0;
			if (max_square < s) {
				max_square = s;
				max_list.clear();
				max_list.emplace_back(i, j, min_size);
			}
			else if(max_square == s){
				max_list.emplace_back(i, j, min_size);
			}
		}
	}

	if (max_list.size() == 1)
	{
		out << (max_square - 1)*D << endl;
		return 0;
	}

	for (auto& i : max_list)
	{
		if (get<2>(i) == 1)
		{
			num_one[1+get<0>(i)][1+get<1>(i)]++;
			num_one[1+get<0>(i)][1+get<1>(i) + D]++;
			num_one[1+get<0>(i) + D][1 + get<1>(i)]++;
			num_one[1+get<0>(i)+D][1 + get<1>(i)+D]++;
		}
		else
		{
			num_error[1+get<0>(i)][1 + get<1>(i)]++;
			num_error[1+get<0>(i)][1 + get<1>(i) + D]++;
			num_error[1+get<0>(i) + D][1 + get<1>(i)]++;
			num_error[1+get<0>(i) + D][1 + get<1>(i) + D]++;
		}
	}
	CuSum(num_one);
	CuSum(num_error);

	using BS_INT = int32_t;
	BS_INT ok_range = D, ng_range = -1;
	while (std::abs(ok_range - ng_range) > 1) {
		BS_INT mid = (ok_range + ng_range) / 2;
		bool is_ok = false;

		for (int32_t i = 1-1; i <= D - 1; i++)
		{
			for (int32_t j = 1-1; j <= D - 1; j++)
			{
				if (get_sum(num_one, i + mid, j + mid, i + D, j + D) == 0 &&
					get_sum(num_error,i,j, i + D, j + D) - get_sum(num_error, i, j, i + mid, j + mid) == 0
					)
				{
					is_ok = true;
					goto break_2;
				}
			}
		}
	break_2:;



		//ここに書く

		if (is_ok) {
			ok_range = mid;
		}
		else {
			ng_range = mid;
		}
	}
	out << (max_square - 1)*D+ok_range-1 << endl;

#if 0
	std::vector<std::tuple<int, int, int>> max_list2;
	max_list2.reserve(max_list.size());
	for (auto& i : max_list) {
		max_list2.emplace_back(std::get<1>(i), std::get<0>(i), get<2>(i));
	}
	std::sort(max_list2.begin(), max_list2.end());


	int32_t min_diff = D;
	for (size_t i = 0; i < max_list.size(); i++)
	{
		if (i > 0 && get<0>(max_list[i]) == get<0>(max_list2[i-1])) { continue; }
		for (size_t j = 0; j < max_list2.size(); j++)
		{
			if (j > 0 && get<0>(max_list2[j]) == get<0>(max_list2[j-1])) { continue; }
			//for (auto& k : max_list)
			//{
			//	used[get<0>(k)][get<1>(k)] = false;
			//}

			auto cir_dec = [&max_list](size_t index) {if (index == 0) { return max_list.size() - 1; } else { return index - 1; }};
			auto cir_inc = [&max_list](size_t index) {if ((++index) == max_list.size()) { return (size_t)0; } else { return index; }};

			size_t k = cir_dec(i);
			for (; k != i; k = cir_dec(k))
			{
				if (get<2>(max_list[k]) == 0) {
					break;
				}
				used[get<0>(max_list[k])][get<1>(max_list[k])] = true;
			}
			size_t l = cir_dec(j);
			for (; k != i; k = cir_inc(k))
			{
				int32_t x_diff = get<0>(max_list[k]) - get<0>(max_list[i]);
				if (x_diff < 0) { x_diff += D; }

				while (get<2>(max_list2[l]) == 1 && used[get<1>(max_list2[l])][get<0>(max_list2[l])] == false && l != j);
				int32_t y_diff = get<0>(max_list[l]) - get<0>(max_list[j]);
				if (y_diff < 0) { y_diff += D; }

				min_diff = std::min(x_diff, y_diff);

				used[get<0>(max_list[k])][get<1>(max_list[k])] = false;
			}

#if 0
			for (size_t k = cir_dec(i); k != i; k= cir_dec(k))
			{
				int32_t x_diff = get<0>(max_list[k]) - get<0>(max_list[i]);
				if (x_diff < 0) { x_diff += D; }
				int32_t y_diff = 0;
				size_t l = cir_dec(j);
				while (get<2>(max_list2[l]) == 1 && used[get<1>(max_list2[l])][get<0>(max_list2[l])]==false && l != j);
				int32_t y_diff = get<0>(max_list[l]) - get<0>(max_list[l]);
				if (y_diff < 0) { y_diff += D; }

				if (get<2>(max_list[k]) == 0) {
					break;
				}
				used[get<0>(max_list[k])][get<1>(max_list[k])] = true;
			}
#endif
		}
	}
	out << (max_square - 1)*D + min_diff << endl;
#endif

	return 0;
}
#endif


Measured memory_bytes: 45548