#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<string>
#include<stack>
#include<cstdio>
#include<cmath>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<int,P> P1;

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define rep(i,x) for(int i=0;i<x;i++)
#define rep1(i,x) for(int i=1;i<=x;i++)
#define rrep(i,x) for(int i=x-1;i>=0;i--)
#define rrep1(i,x) for(int i=x;i>0;i--)
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
#define mp1(a,b,c) P1(a,P(b,c))

const int INF=1000000000;
const int dir_4[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
const int dir_8[8][2]={{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};

int main(){
	static int N,D;
	static int x[100010],y[100010];
	scanf("%d%d",&N,&D);
	for(int i = 1 ; i <= N ; i ++){
		scanf("%d%d",&x[i],&y[i]);
	}
	
	static int cnt[1002][1002] = {};
	for(int i = 1 ; i <= N ; i ++){
		cnt[x[i]%D][y[i]%D] ++;
	}
	
	static int A[1002][1002] = {},B[1002][1002] = {};
	for(int i = 0 ; i < D ; i ++){
		for(int j = 0 ; j < D ; j ++){
			while(1){
				if(A[i][j]*B[i][j] >= cnt[i][j])break;
				A[i][j] ++;
				if(A[i][j]*B[i][j] >= cnt[i][j])break;
				B[i][j] ++;
			}
		}
	}
	
	int M = 0, l = 0, r = D-1;
	for(int i = 0 ; i < D ; i ++){
		for(int j = 0 ; j < D ; j ++){
			M = max( M , A[i][j]-1 );
		}
	}
	static int imos[1002][1002] = {};
	while(l < r){
		int m = (l+r)/2;
		for(int i = 0 ; i < D ; i ++){
			for(int j = 0 ; j < D ; j ++){
				imos[i][j] = 0;
			}
		}
		int CNT = 0;
		for(int i = 0 ; i < D ; i ++){
			for(int j = 0 ; j < D ; j ++){
				if(A[i][j] == M+1){
					CNT ++;
					if(B[i][j] == M+1){
						vector<P> X;
						vector<P> Y;
						if(i < m){
							X.push_back(P(i-m+D,D-1));
							X.push_back(P(0,i));
						}
						else X.push_back(P(i-m,i));
						if(j < m){
							Y.push_back(P(j-m+D,D-1));
							Y.push_back(P(0,j));
						}
						else Y.push_back(P(j-m,j));
						for(P p: X)for(P q: Y){
							imos[p.fr][q.fr] ++;
							imos[p.fr][q.sc+1] --;
							imos[p.sc+1][q.fr] --;
							imos[p.sc+1][q.sc+1] ++;
						}
					}
					else {
						vector<P> X;
						vector<P> Y;
						if(i < m){
							X.push_back(P(i+1,i-m+D-1));
						}
						else {
							X.push_back(P(0,i-m-1));
							X.push_back(P(i+1,D-1));
						}
						if(j < m){
							Y.push_back(P(j+1,j-m+D-1));
						}
						else {
							Y.push_back(P(0,j-m-1));
							Y.push_back(P(j+1,D-1));
						}
						for(P p: X)for(P q: Y){
							imos[p.fr][q.fr] --;
							imos[p.fr][q.sc+1] ++;
							imos[p.sc+1][q.fr] ++;
							imos[p.sc+1][q.sc+1] --;
						}
						imos[0][0] ++;
						imos[0][D] --;
						imos[D][0] --;
						imos[D][D] ++;
					}
				}
			}
		}
		for(int i = 0 ; i < D ; i ++){
			for(int j = 0 ; j < D ; j ++){
				imos[i+1][j] += imos[i][j];
			}
		}
		for(int i = 0 ; i < D ; i ++){
			for(int j = 0 ; j < D ; j ++){
				imos[i][j+1] += imos[i][j];
			}
		}
		bool b = false;
		for(int i = 0 ; i < D ; i ++){
			for(int j = 0 ; j < D ; j ++){
				if(imos[i][j] == CNT){
					b = true;
					break;
				}
			}
		}
		if(b)r = m;
		else l = m+1;
	}
	cout << M*D+l << endl;
}


Measured memory_bytes: 16768