#include<iostream>
#include<cstring>
using namespace std;

int n,d,v[3000][3000],s[3][3000][3000];

int S(int x1,int y1,int x2,int y2,int t)
{
	return s[t][x2][y2]-s[t][x2][y1-1]-s[t][x1-1][y2]+s[t][x1-1][y1-1];
}

int check(int x)
{
	int r=x%d;
	for(int i=1;i<=d;i++)
		for(int j=1;j<=d;j++)
		{
			int x1=i,y1=j,x2=x1+r,y2=y1+r,x3=x1+d-1,y3=y1+d-1;
			if(!S(x1,y2+1,x3,y3,1)&&!S(x2+1,y1,x3,y3,1)&&!S(x2+1,y2+1,x3,y3,0))
				return 1;
		}
	return 0;
}
int main()
{
	scanf("%d%d",&n,&d);
	memset(v,0,sizeof v);
	for(int i=0;i<n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		v[x%d+1][y%d+1]++;
	}
	int Mx=0,t;
	for(int i=1;i<=d;i++)
		for(int j=1;j<=d;j++)
			v[i+d][j]=v[i][j+d]=v[i+d][j+d]=v[i][j],Mx=max(Mx,v[i][j]);
	for(t=0;(t+1)*(t+1)<Mx;t++);
	int l[3]={t*t+1,t*(t+1)+1,1e9};
	for(int i=1;i<=d*2;i++)
		for(int j=1;j<=d*2;j++)
			for(int t=0;t<2;t++)
			{
				s[t][i][j]=s[t][i-1][j]+s[t][i][j-1]-s[t][i-1][j-1];
				if(l[t]<=v[i][j])
					s[t][i][j]++;
			}
	int L=t*d,R=t*d+d,ans=R,mid;
	while(L<=R)
		if(check(mid=(L+R)>>1))
			R=mid-1,ans=mid;
		else
			L=mid+1;
	cout<<ans;
	return 0;
}