#include <bits/stdc++.h>
using namespace std;
int n,m;
pair<int,int>a[1000010];
vector<int>b,c,d,e;
int b1,c1;
int ans;
int main()
{
    freopen("card.in","r",stdin);
    freopen("card.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i].first;
    for(int i=1;i<=n;i++) cin>>a[i].second;
    ans=a[n].first-a[1].first;
    b.push_back(a[1].first);
    d.push_back(a[1].first);
    b1++;
    if(a[1].second>a[1].first)
    {
        b.push_back(a[1].second);
        d.push_back(a[1].second);
        b1++;
        for(int i=2;i<=n;i++)
        {
            if(a[i].second>a[i].first)
            {
                if(a[i].first>b[b1-1]) break;
                else
                {
                    b.push_back(min(a[i].second,b[b1-1]));
                    d.push_back(max(d[b1-1],a[i].second));
                    b1++;
                    b[b1-2]=min(b[b1-2],a[i].first);
                }
            }
            else
            {
                b[b1-1]=min(b[b1-1],a[i].first);
                break;
            }
        }
    }
    c.push_back(a[n].first);
    e.push_back(a[n].first);
    c1++;
    if(a[n].second<a[n].first)
    {
        c.push_back(a[n].second);
        e.push_back(a[n].second);
        c1++;
        for(int i=n-1;i>0;i--)
        {
            if(a[i].second<a[i].first)
            {
                if(a[i].first<c[c1-1]) break;
                else
                {
                    c.push_back(max(a[i].second,c[c1-1]));
                    e.push_back(min(e[c1-1],a[i].second));
                    c1++;
                    c[c1-2]=max(c[c1-2],a[i].first);
                }
            }
            else
            {
                c[c1-1]=max(c[c1-1],a[i].first);
                break;
            }
        }
    }
    for(int i=0;i<=m;i++)
    {
        int b2=min(i,b1-1),c2=min(m-i,c1-1);
        ans=min(ans,max(c[c2],d[b2])-min(b[b2],e[c2]));
    }
    cout<<ans;
    return 0;
}