#include <bits/stdc++.h>
using namespace std ;
const int NR = 1e5 + 5 ;
int n , d , maxn , minn = 1e6 ;
struct node
{
	int x , y ;
}	a[NR] ;
bool cmp(node a , node b)
{
	if(a.x != b.x)	return a.x < b.x ;
	return a.y < b.y ;
}
bool check(int len)
{
	deque <int> dx , dn ;
	for(int i = 1 ; i <= n ; i++)
	{
		while(a[i].x == a[i + 1].x && i < n)
		{
			while(!dx.empty() && a[dx.back()].y <= a[i].y)	dx.pop_back() ;
			dx.push_back(i) ;
			while(!dx.empty() && a[i].x - a[dx.front()].x > len)	dx.pop_front() ;
			while(!dn.empty() && a[dn.back()].y >= a[i].y)	dn.pop_back() ;
			dn.push_back(i) ;
			while(!dn.empty() && a[i].x - a[dn.front()].x > len)	dn.pop_front() ;
			i++ ;
		}
		while(!dx.empty() && a[dx.back()].y <= a[i].y)	dx.pop_back() ;
		dx.push_back(i) ;
		while(!dx.empty() && a[i].x - a[dx.front()].x > len)	dx.pop_front() ;
		while(!dn.empty() && a[dn.back()].y >= a[i].y)	dn.pop_back() ;
		dn.push_back(i) ;
		while(!dn.empty() && a[i].x - a[dn.front()].x > len)	dn.pop_front() ;
		if(a[dx.front()].y - a[dn.front()].y + 1 >= d)	return 1 ;
	}
	return 0 ;
}
int main()
{
	cin >> n >> d ;
	for(int i = 1 ; i <= n ; i++)
	{
		cin >> a[i].x >> a[i].y ;
		maxn = max(maxn , a[i].y) ;
		minn = min(minn , a[i].y) ;
	}
	if(maxn - minn < d)
	{
		cout << -1 ;
		return 0 ;
	}
	sort(a + 1 , a + n + 1 , cmp) ;
	int l = 1 , r = a[n].x ;
	while(l < r)
	{
		int mid = (l + r) >> 1 ;
		if(check(mid))	r = mid ;
		else	l = mid + 1 ;
	}
	cout << l ;
	return 0 ;
}