#include<bits/stdc++.h>
using namespace std;
int n,m,a[1000005],b[1000005],d[2000005],p[1000005],r,ss,ps;
struct nm{
    int v,id,ab;
}t[2000005];
bool cp(nm x,nm y){
    return x.v<y.v;
}
inline bool f(int x){
    r=ss=ps=0;
    for(int i=1;i<=n;i++) p[i]=0;
    for(int i=1;i<=n;i++){
        if(i>1){
            if(a[t[i-1].id]<i&&b[t[i-1].id]<i) return false;
            if(p[t[i-1].id]==3){
                if(t[i-1].ab==1) ps++,p[t[i-1].id]=2;
                else p[t[i-1].id]=1;
            }else{
                ss--;
                if(t[i-1].ab==2) ps--;
                p[t[i-1].id]=0;
            }
        }
        while(t[r+1].v-t[i].v<=x){
            r++;
            if(!p[t[r].id]){
                ss++,p[t[r].id]=t[r].ab;
                if(t[r].ab==2) ps++;
            }else{
                if(t[r].ab==1) ps--;
                p[t[r].id]=3;
            }
        }
        if(ss>=n&&ps<=m) return true;
    }
    return false;
} 
int main(){
    freopen("card.in","r",stdin);
    freopen("card.out","w",stdout);
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    for(int i=1;i<=n;i++) t[i*2-1]={a[i],i,1},t[i*2]={b[i],i,2};
    sort(t+1,t+n+n+1,cp);
    for(int i=1;i<=n+n;i++) d[i]=t[i].v;
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(d+1,d+n+n+1,a[i])-d;
        b[i]=lower_bound(d+1,d+n+n+1,b[i])-d;
    }
    int l=0,r=t[n+n].v-t[1].v,md;
    while(l<=r){
        md=(l+r)>>1;
        if(f(md)) r=md-1;
        else l=md+1;
    }
    cout<<r+1;
    return 0;
}