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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

int N,D;

int cnt[1111][1111];
int acc[2222][2222];
int uku[111111];

signed main(){
	for(int i=1;i<111111;i++){
		uku[i]=uku[i-1];
		if(uku[i]*uku[i]<i)uku[i]++;
	}

	cin>>N>>D;

	int L=0;
	rep(i,N){
		int x,y;
		cin>>x>>y;
		x%=D;y%=D;
		cnt[y][x]++;
		chmax(L,uku[cnt[y][x]]);		
	}

	vpint f,h;
	rep(i,D)rep(j,D){
		if((L-1)*(L-1)>=cnt[i][j])continue;
		if(L*(L-1)>=cnt[i][j])h.pb({i,j});
		else f.pb({i,j});
	}

	int lb=0,ub=D;
	while(ub-lb>1){
		int mid=(lb+ub)/2;

		memset(acc,0,sizeof(acc));
		for(auto &p:f){
			int y,x;
			tie(y,x)=p;
			acc[y][x]++;
			acc[y+mid][x]--;
			acc[y][x+mid]--;
			acc[y+mid][x+mid]++;
		}
		for(auto &p:h){
			int y,x;
			tie(y,x)=p;

			acc[y][x]++;
			acc[y+mid][x]--;
			acc[y][x+D]--;
			acc[y+mid][x+D]++;

			acc[y][x]++;
			acc[y+D][x]--;
			acc[y][x+mid]--;
			acc[y+D][x+mid]++;

			acc[y][x]--;
			acc[y+mid][x]++;
			acc[y][x+mid]++;
			acc[y+mid][x+mid]--;			
		}
		rep(i,D*2)rep(j,D*2){
			acc[i+1][j]+=acc[i][j];
			acc[i][j+1]+=acc[i][j];
			acc[i+1][j+1]-=acc[i][j];
		}
		bool ok=false;
		rep(i,D)rep(j,D)if(acc[i][j]+acc[i+D][j]+acc[i][j+D]+acc[i+D][j+D]==h.size()+f.size())ok=true;
		if(ok)ub=mid;
		else lb=mid;
	}

	cout<<(L-1)*D+ub-1<<endl;
	return 0;
}