#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 1005
#define ll long long
#define ld double
#define mod 998244353
using namespace std;	
int n, d;
int tu(int x)
{
	int res = x % d;
	if(res == 0) res += d;
	return res; 
}
struct th
{
	int a[maxn][maxn];
	th()
	{
		memset(a, 0, sizeof(a));
	}
	void ins(int x, int y)
	{
		a[x][y]++;
	}
	void build()
	{
		for(int i = 1; i <= d; i++)
			for(int j = 1; j <= d; j++)
				a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
	}
	int q(int l, int r, int x, int y)
	{
		int ans = a[r][y] - a[l - 1][y] - a[r][x - 1] + a[l - 1][x - 1];
		return ans;	
	} 
}q1, q2;
int s[maxn][maxn];
bool check(int t)
{
	for(int i = 1; i <= d; i++)
		for(int j = 1; j <= d; j++)
		{
			int tp[2][3], pl[2][4];
			pl[0][3] = pl[1][3] = d + 1;
			pl[0][0] = pl[1][0] = 1;
			if(i + t <= d + 1)
				tp[0][0] = 0, tp[0][1] = 1, tp[0][2] = 0, 
				pl[0][1] = i, pl[0][2] = i + t;
			else
				tp[0][0] = 1, tp[0][1] = 0, tp[0][2] = 1, 
				pl[0][1] = i + t - d, pl[0][2] = i;
			
			if(j + t <= d + 1)	
				tp[1][0] = 0, tp[1][1] = 1, tp[1][2] = 0, 
				pl[1][1] = j, pl[1][2] = j + t;	
			else
				tp[1][0] = 1, tp[1][1] = 0, tp[1][2] = 1, 
				pl[1][1] = j + t - d, pl[1][2] = j;
			bool fl = 1;
			for(int x = 0; x < 3; x++)
				for(int y = 0; y < 3; y++)
					if(tp[0][x] && tp[1][y]) continue;
					else
					{
						if(tp[0][x] + tp[1][y]) 
						{
							if(q1.q(pl[0][x], pl[0][x + 1] - 1, pl[1][y], pl[1][y + 1] - 1)) fl = 0;
						}
						else
							if(q2.q(pl[0][x], pl[0][x + 1] - 1, pl[1][y], pl[1][y + 1] - 1)) fl = 0;
					}
			if(fl) 
			{
			//	cout<<"CAN"<<i<<" "<<j<<" "<<t<<endl; 
				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);
		s[tu(x)][tu(y)]++;
	}
	int mxs = 0;
	for(int i = 1; i <= d; i++)
		for(int j = 1; j <= d; j++)
			mxs = max(mxs, s[i][j]);
	int ns = 1;
	while(ns * ns < mxs) ns++;
	for(int i = 1; i <= d; i++)
		for(int j = 1; j <= d; j++)
		{
			if(ns * (ns - 1) < s[i][j]) q1.ins(i, j);
			if((ns - 1) * (ns - 1) < s[i][j]) q2.ins(i, j);
		}
	q1.build(), q2.build();
	int l = 1, r = d;
	while(l < r)
	{
		int mid = (l + r) >> 1;
		if(check(mid)) r = mid;
		else l = mid + 1;
	}
	printf("%d\n", (ns - 1) * d + l - 1);
	return 0;
} 
/*
bbbbbb
bababa

*/