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

using ll=int64_t;
#define int ll

#define FOR(i,a,b) for(int i=int(a);i<int(b);i++)
#define REP(i,b) FOR(i,0,b)
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define ALL(x) x.begin(),x.end()
auto& errStream=cerr;
#ifdef LOCAL
#define cerr (cerr<<"-- line "<<__LINE__<<" -- ")
#else
class CerrDummy{}cerrDummy;
template<class T>
CerrDummy& operator<<(CerrDummy&cd,const T&){
	return cd;
}
using charTDummy=char;
using traitsDummy=char_traits<charTDummy>;
CerrDummy& operator<<(CerrDummy&cd,basic_ostream<charTDummy,traitsDummy>&(basic_ostream<charTDummy,traitsDummy>&)){
	return cd;
}
#define cerr cerrDummy
#endif
#define REACH cerr<<"reached"<<endl
#define DMP(x) cerr<<#x<<":"<<x<<endl
#define ZERO(x) memset(x,0,sizeof(x))
#define ONE(x) memset(x,-1,sizeof(x))

using pi=pair<int,int>;
using vi=vector<int>;
using ld=long double;

template<class T,class U>
ostream& operator<<(ostream& os,const pair<T,U>& p){
	os<<"("<<p.first<<","<<p.second<<")";
	return os;
}

template<class T>
ostream& operator <<(ostream& os,const vector<T>& v){
	os<<"{";
	REP(i,(int)v.size()){
		if(i)os<<",";
		os<<v[i];
	}
	os<<"}";
	return os;
}

ll read(){
	ll i;
	scanf("%"  SCNd64,&i);
	return i;
}

void printSpace(){
	printf(" ");
}

void printEoln(){
	printf("\n");
}

void print(ll x,int suc=1){
	printf("%" PRId64,x);
	if(suc==1)
		printEoln();
	if(suc==2)
		printSpace();
}

string readString(){
	static char buf[3341000];
	scanf("%s",buf);
	return string(buf);
}

char* readCharArray(){
	static char buf[3341000];
	static int bufUsed=0;
	char* ret=buf+bufUsed;
	scanf("%s",ret);
	bufUsed+=strlen(ret)+1;
	return ret;
}

template<class T,class U>
void chmax(T& a,U b){
	if(a<b)
		a=b;
}

template<class T,class U>
void chmin(T& a,U b){
	if(b<a)
		a=b;
}

template<class T>
T Sq(const T& t){
	return t*t;
}

#define CAPITAL
void Yes(bool ex=true){
	#ifdef CAPITAL
	cout<<"YES"<<endl;
	#else
	cout<<"Yes"<<endl;
	#endif
	if(ex)exit(0);
}
void No(bool ex=true){
	#ifdef CAPITAL
	cout<<"NO"<<endl;
	#else
	cout<<"No"<<endl;
	#endif
	if(ex)exit(0);
}

const ll infLL=LLONG_MAX/3;

#ifdef int
const int inf=infLL;
#else
const int inf=INT_MAX/2-100;
#endif

const int Nmax=1010;
int d,buf[3][Nmax][Nmax];
int GetSum(int k,int y1,int y2,int x1,int x2){
	int res=buf[k][y2-1][x2-1];
	if(y1-1>=0)
		res-=buf[k][y1-1][x2-1];
	if(x1-1>=0)
		res-=buf[k][y2-1][x1-1];
	if(y1-1>=0&&x1-1>=0)
		res+=buf[k][y1-1][x1-1];
	return res;
}
int Wafrelka(int k,int y1,int y2,int x1,int x2){
	if(y2<=y1)return 0;
	if(x2<=x1)return 0;
	if(y1>=d){
		return Wafrelka(k,y1-d,y2-d,x1,x2);
	}
	if(x1>=d){
		return Wafrelka(k,y1,y2,x1-d,x2-d);
	}
	if(y2>d){
		return Wafrelka(k,y1,d,x1,x2)+Wafrelka(k,0,y2-d,x1,x2);
	}
	if(x2>d){
		return Wafrelka(k,y1,y2,x1,d)+Wafrelka(k,y1,y2,0,x2-d);
	}
	return GetSum(k,y1,y2,x1,x2);
}
void Prepare(int k){
	REP(y,d)REP(x,d)
		buf[k][y][x+1]+=buf[k][y][x];
	REP(y,d)REP(x,d)
		buf[k][y+1][x]+=buf[k][y][x];
}
bool Ok(const int mid,const vector<vi>&cnt){
	cerr<<mid<<endl;
	ZERO(buf);
	int p=mid/d;
	int q=d-mid%d;
	REP(y,d)REP(x,d){
		if(cnt[y][x]<=p*p){
			cerr<<0<<endl;
			buf[0][y][x]++;
		}else if(cnt[y][x]<=p*(p+1)){
			cerr<<1<<endl;
			buf[1][y][x]++;
		}else if(cnt[y][x]<=(p+1)*(p+1)){
			cerr<<2<<endl;
			buf[2][y][x]++;
		}else
			return false;
	}
	REP(k,3)
		Prepare(k);
	REP(y,d)REP(x,d){
		int a00=Wafrelka(1,y,y+q,x,x+q)+Wafrelka(2,y,y+q,x,x+q);
		int a01=Wafrelka(2,y,y+q,x+q,x+d);
		int a10=Wafrelka(2,y+q,y+d,x,x+q);
		if(a00==0&&a01==0&&a10==0)
			return true;
	}
	return false;
}

signed main(){
	int n=read();
	d=read();
	vector<vi> cnt(d,vi(d,0));
	REP(i,n){
		int x=read(),y=read();
		cnt[y%d][x%d]++;
	}
	int low=0,high=d*n;
	while(high-low>1){
		const int mid=(low+high)/2;
		if(Ok(mid,cnt)){
			high=mid;
		}else{
			low=mid;
		}
	}
	print(high-1);
}


Measured memory_bytes: 32640