#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10,K=22;
int n,m,a[N],b[N],mi[N],mx[N],qmx[N],st[N][K],lg[N];
set<int> s,t;
void init()
{
    for (int i=2;i<=n;i++) lg[i]=lg[i/2]+1;
    for (int j=1;j<=20;j++)
    {
        for (int i=1;i+(1<<j)-1<=n;i++) st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
    }
}
int solve(int x,int y)
{
//    cout<<x<<" "<<y<<endl;
    if (x>y) return -1;
    int k=lg[y-x+1];
    return max(st[x][k],st[y-(1<<k)+1][k]);
}
int get(int i,int x)
{
    return max(n-(m-i)+1,max(x,i+1));
}
int main() {
    freopen("card.in","r",stdin);
    freopen("card.out","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n>>m;
    for (int i=1;i<=n;i++) cin>>a[i],s.insert(a[i]),mx[i]=max(mx[i-1],a[i]),st[i][0]=a[i];
    for (int i=1;i<=n;i++) cin>>b[i];
    init();
    mi[n]=b[n];qmx[n]=min(a[n],b[n]);
    for (int i=n-1;i>=1;i--) mi[i]=min(b[i],mi[i+1]),qmx[i]=max(qmx[i+1],min(a[i],b[i])); 
    int ans=1e9;
    for (int i=n;i>=n-m+1;i--)
    {
        auto it=s.end();it--;
        auto it1=s.begin();
        ans=min(ans,*it-*it1);
        s.erase(a[i]),s.insert(b[i]);
    }
    auto it=s.end();it--;
    auto it1=s.begin();
    ans=min(ans,*it-*it1);
    s.clear();
    for (int i=1;i<=n;i++) s.insert(a[i]);
    for (int i=1;i<=m;i++)
    {
        s.erase(a[i]),s.insert(b[i]),t.insert(b[i]);
        auto it=s.begin();
        int x=lower_bound(mi+1,mi+n+1,*it)-mi;
        if (x<=n)
        {
            auto it1=t.end();it1--;
//            cout<<"qwq "<<get(i,x)<<" "<<*it1<<" "<<solve(i+1,get(i,x)-1)<<" "<<qmx[get(i,x)]<<endl;
            ans=min(ans,max(max(*it1,solve(i+1,get(i,x)-1)),qmx[get(i,x)])-*it);
        }
//      cout<<ans<<endl;
    }
    cout<<ans;
}