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

#define ll long long

ll n,m,lest,li,sest=1145141919810,si,las,ans=1145141919810;
bool check[500050];

struct itv{
    ll l,r,len;
}a[500050];

bool cmp(itv a,itv b){
    return a.len>b.len;
}

void dfs(ll x,ll cl,ll cr){
    if(x==m+1){
        ans=min(ans,lest-sest);
    }else{
        for(ll i=1;i<=n;i++){
            if(a[i].l>cr||a[i].r<cl||check[i]){
                continue;
            }
            check[i]=1;
            lest=max(a[i].len,lest);
            sest=min(a[i].len,sest);
            ll tl=lest,ts=sest;
            dfs(x+1,max(cl,a[i].l),min(cr,a[i].l));
            lest=tl,sest=ts;
            check[i]=0;
        }
    }
}

int main(){
    cin>>n>>m;
    for(ll i=1;i<=n;i++){
        cin>>a[i].l>>a[i].r;
        a[i].len=a[i].r-a[i].l;
    }
    sort(a+1,a+n+1,cmp);
    dfs(1,0,1e9);
    cout<<ans;
    return 0;
}