#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int cnt[1111][1111];
int rot[1210100];
typedef pair<int, int>pii;
int maxis[1111];
int get(vector<pii>v1, vector<pii>v2, int hen)
{
	for (int i = 0; i < hen; i++)maxis[i] = 0;
	for (int i = 0; i < v1.size(); i++)
	{
		if (v1[i].first < v1[i].second)
		{
			maxis[0] = max(maxis[0], v1[i].first);
			maxis[v1[i].first + 1] = max(maxis[v1[i].first + 1], v1[i].second);
			maxis[v1[i].second + 1] = max(maxis[v1[i].second + 1], v1[i].first + hen);
		}
		else
		{
			maxis[0] = max(maxis[0], v1[i].second);
			maxis[v1[i].second + 1] = max(maxis[v1[i].second + 1], v1[i].first);
			maxis[v1[i].first + 1] = max(maxis[v1[i].first + 1], v1[i].second + hen);
		}
	}
	for (int i = 0; i < v2.size(); i++)
	{
		if (v2[i].first < v2[i].second)
		{
			maxis[0] = max(maxis[0], v2[i].second);
			maxis[v2[i].first + 1] = max(maxis[v2[i].first + 1], v2[i].first+hen);
			maxis[v2[i].second + 1] = max(maxis[v2[i].second + 1], v2[i].second + hen);
		}
		else
		{
			maxis[0] = max(maxis[0], v2[i].first);
			maxis[v2[i].first + 1] = max(maxis[v2[i].first + 1], v2[i].first + hen);
			maxis[v2[i].second + 1] = max(maxis[v2[i].second + 1], v2[i].second + hen);
		}
	}
	int mini = 1000000000;
	for (int i = 0; i < hen; i++)
	{
		mini = min(mini, maxis[i] - i);
		maxis[i + 1] = max(maxis[i + 1], maxis[i]);
	}
	return mini;
}
int main()
{
	int num, hen;
	scanf("%d%d", &num, &hen);
	for (int i = 0; i < num; i++)
	{
		int za, zb;
		scanf("%d%d", &za, &zb);
		cnt[za%hen][zb%hen]++;
	}
	for (int i = 1; i < 1050; i++)
	{
		for (int j = (i - 1)*(i - 1) + 1; j <= i*i; j++)rot[j] = i;
	}
	vector<pii>v1, v2;
	int maxi = -1;
	for (int i = 0; i < hen; i++)
	{
		for (int j = 0; j < hen; j++)
		{
			if (cnt[i][j]>0)
			{
				int l = rot[cnt[i][j]] - 1;
				if (maxi < l)v1.clear(), v2.clear(), maxi = l;
				if (maxi == l)
				{
					if (cnt[i][j] <= l*(l + 1))v1.push_back(make_pair(i, j));
					else v2.push_back(make_pair(i, j));
				}
			}
		}
	}
	int mini = 1000000000;
	for (int i = 0; i < hen; i++)
	{
		for (int j = 0; j < v1.size(); j++)v1[j].first = (v1[j].first + 1) % hen;
		for (int j = 0; j < v2.size(); j++)v2[j].first = (v2[j].first + 1) % hen;
		mini = min(mini, get(v1, v2, hen));
	}
	printf("%d\n", mini + hen*maxi);
}