#include<bits/stdc++.h>
using namespace std;
const int N=5e5;
int n,m,mina=N*200;
/*struct node{
    int l,r,w;
}a[N];
struct code{
    int w,id;
    bool tb;
}c[N*2];
int n,m,cnt,tot;
bool cmpa(node a,node b){
	return a.w<b.w;
}
bool cmpb(code a,code b){
	return a.w<b.w;
}
struct tree{
	int v,lz;
}f[N*16];
void pushdown(int p){
    if(f[p].lz){
        f[p<<1].lz+=f[p].lz;
		f[p<<1^1].lz+=f[p].lz;
        f[p<<1].v+=f[p].lz;
		f[p<<1|1].v+=f[p].lz;
        f[p].lz=0;
    }
}
void update(int p,int l,int r,int x,int y,int k){
    if(l>=x&&r<=y){
        f[p].v+=k;
		f[p].lz+=k;
        pushdown(p);
        return;
    }
    int mid=(l+r)>>1;
	pushdown(p);
    if (y<=mid) update(p<<1,l,mid,x,y,k);
    else if (x>mid) update(p<<1|1,mid+1,r,x,y,k);
    else update(p<<1,l,mid,x,y,k),update(p<<1|1,mid+1,r,x,y,k);
    f[p].v=max(f[p<<1].v,f[p<<1|1].v);
}
int l,r,mid,ans;*/	
struct xd{
	int l,r,w;
}f[N];
struct node{
	int w;
	int ma,mi,df;
}a[100000];
bool cmp(xd x,xd y){
	return x.w<y.w;
}
int main(){
	freopen("interval.in","r",stdin);
	freopen("interval.out","w",stdout);
	std::cin>>n>>m;
	for(int i=1;i<=n;i++){
		std::cin>>f[i].l>>f[i].r;
		f[i].w=f[i].r-f[i].l;
		for(int j=f[i].l;j<=f[i].r;j++){
			a[j].w++;
		}
	}
	sort(f+1,f+1+n,cmp);
	
	for(int i=1;i<=100000;i++){
		if(a[i].w<m) continue;
		int minn=N*200;
		for(int j=1;j<=n-m+1;j++){
			if(f[j].l<=i&&f[j].r>=i&&f[j+m-1].l<=i&&f[j+m-1].r>=i)
			minn=min(minn,f[j+m-1].w-f[j].w);
		}
		mina=min(mina,minn);
	}
	std::cout<<mina<<endl;
	return 0;
}