#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
using namespace std;
 
#define mod 1000000007
#define FOR(x,to) for(int x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define long long long
inline int rei(){int x;cin>>x;return x;}
inline long rel(){long x;cin>>x;return x;}
inline string res(){string x;cin>>x;return x;}
//------------------------------------------------------- 
int Num[1000000];
int D;
int Map2[1000000];
int Map3[1000000];
int C2;
int C3;
int Mapsum2(int l,int r,int d,int u){
	int c = Map2[r*D+u];
	if(l != 0){
		c -= Map2[(l-1)*D+u];
	}
	if(d != 0){
		c -= Map2[r*D+d-1];
	}
	if(l != 0 && d != 0){
		c += Map2[(l-1)*D+d-1];
	}
	return c;
}
int Mapsum3(int l,int r,int d,int u){
	int c = Map3[r*D+u];
	if(l != 0){
		c -= Map3[(l-1)*D+u];
	}
	if(d != 0){
		c -= Map3[r*D+d-1];
	}
	if(l != 0 && d != 0){
		c += Map3[(l-1)*D+d-1];
	}
	return c;
}
int MapSum2(int l,int r,int d,int u){
	if(u >= D){
		if(r >= D){
			return Mapsum2(0,r-D,0,u-D) + Mapsum2(l,D-1,d,D-1) + Mapsum2(0,r-D,d,D-1) + Mapsum2(l,D-1,0,u-D);
		}
		else{
			return Mapsum2(l,r,0,u-D) + Mapsum2(l,r,d,D-1);
		}
	}
	else{
		if(r >= D){
			return Mapsum2(0,r-D,d,u) + Mapsum2(l,D-1,d,u);
		}
		else{
			return Mapsum2(l,r,d,u);
		}
	}
}
int MapSum3(int l,int r,int d,int u){
	if(u >= D){
		if(r >= D){
			return Mapsum3(0,r-D,0,u-D) + Mapsum3(l,D-1,d,D-1) + Mapsum3(0,r-D,d,D-1) + Mapsum3(l,D-1,0,u-D);
		}
		else{
			return Mapsum3(l,r,0,u-D) + Mapsum3(l,r,d,D-1);
		}
	}
	else{
		if(r >= D){
			return Mapsum3(0,r-D,d,u) + Mapsum3(l,D-1,d,u);
		}
		else{
			return Mapsum3(l,r,d,u);
		}
	}
}
bool check(int bc){
	for(int i=0;i<D;i++){
		for(int j=0;j<D;j++){
			int c2 = MapSum2(0,D-1,j,j+bc-1) + MapSum2(i,i+bc-1,0,D-1) - MapSum2(i,i+bc-1,j,j+bc-1);
			int c3 = MapSum3(i,i+bc-1,j,j+bc-1);
			if(c2 == C2 && c3 == C3){
				return true;
			}
		}
	}
	return false;
}
void Calc(){
	int N = rei();
	D = rei();
	for(int i=0;i<N;i++){
		int x = rei();
		int y = rei();
		Num[(x % D) * D + y % D]++;
	}
	int maxN = 0;
	for(int i=0;i<D*D;i++){
		maxN = max(maxN,Num[i]);
	}
	int oneline;
	for(oneline=0;;oneline++){
		if(oneline*oneline >= maxN){
			break;
		}
	}
	long c1 = (oneline-1)*(oneline-1);
	long c2 = (oneline-1)*oneline;
	long c3 = oneline*oneline;
	for(int i=0;i<D*D;i++){
		if(Num[i] > c2){
			Map3[i]++;
			C3++;
		}
		else if(Num[i] > c1){
			Map2[i]++;
			C2++;
		}
	}
	for(int i=0;i<D*D;i++){
		if(i/D != 0){
			Map2[i] += Map2[i-D];
			Map3[i] += Map3[i-D];
		}
		if(i%D != 0){
			Map2[i] += Map2[i-1];
			Map3[i] += Map3[i-1];
		}
		if((i%D != 0) && (i/D != 0)){
			Map2[i] -= Map2[i-D-1];
			Map3[i] -= Map3[i-D-1];
		}
	}
	int bf = 1;
	int bl = D;
	while(bf != bl){
		long bc = (bf+bl)/2;
		if(check(bc)){
			bl = bc;
		}
		else{
			bf = bc+1;
		}
	}
	cout << bf-1 + (oneline-1)*D << endl;
}
int main(int argc,char** argv){
	ios::sync_with_stdio(false), cin.tie(0);
	cout.tie(0); Calc(); return 0;
}

Measured memory_bytes: 12032