#include<bits/stdc++.h>
using namespace std;
int n,d,dp[1000005][30],dp2[1000005][30],lg[1000005];
struct node{
	int x,y;
}water[1000005];
void RMQ(){
	for(int j=1; j<=lg[n]; j++)
	    for(int i=1; i+(1<<j)-1<=1000000; i++)
	        dp[i][j]=max(dp[i][j-1],dp[i+(1<<j-1)][j-1]),dp2[i][j]=min(dp2[i][j-1],dp2[i+(1<<j-1)][j-1]);
}
bool check(int x){
	int lt,rt,mini,maxi,len;
	for(int i=1; i<=n; i++){
	    lt=water[i].x;
	    rt=lt+x;
	    len=lg[rt-lt+1];
	    maxi=max(dp[lt][len],dp[rt-(1<<len)+1][len]);
	    mini=min(dp2[lt][len],dp2[rt-(1<<len)+1][len]);
		if(abs(maxi-mini)>=x)
		    return true;
	}
	return false;
}
signed main(){
	cin>>n>>d;
	lg[0]=-1;
	for(int i=1; i<=n; i++){
	    cin>>water[i].x>>water[i].y;
	    lg[i]=lg[i>>1]+1;
	    dp2[i][0]=dp[i][0]=water[i].y;
	}
	RMQ();
	int lt=-1,rt=1e6+1;
	while(lt+1<rt){
		int mid=(lt+rt)>>1;
		if(check(mid)==true)
		    rt=mid;
		else 
		    lt=mid;
	}
	if(rt!=1e6+1)
	    cout<<rt;
	else
	    cout<<-1;
	return 0;
}