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

struct node{
	ll a,b;
}t[1100000];

ll n,m;
ll qma[1100000],qmi[1100000],hma[1100000],hmi[1100000];
ll mii,maa,lmi,lma;
ll ans;

bool check(ll mid){
	for (int l=1,r=1;r<=n;r++){
		while (t[r].a-t[l].a>mid&&l<r) l++;
		if (l-1+n-r>m) continue;
		ll n1,n2;
		n1=max({qma[l-1],hma[r+1],t[r].a});
		n2=min({qmi[l-1],hmi[r+1],t[l].a});
		if (n1-n2<=mid) return 1;
	}
	return 0;
}

int main(){
	freopen("card.in","r",stdin);
	freopen("card.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>t[i].a;
	}
	for(int i=1;i<=n;i++){
		cin>>t[i].b;
	}
	qmi[0]=1e18;
	hmi[n+1]=1e18;
	for (int i=1;i<=n;i++){
		qma[i]=max(qma[i-1],t[i].b);
		qmi[i]=min(qmi[i-1],t[i].b);
	}
	for (int i=n;i>=1;i--){
		hma[i]=max(hma[i+1],t[i].b);
		hmi[i]=min(hmi[i+1],t[i].b);
	}
	for (int al=0,ar=1e9;al<=ar;){
		ll mid=(al+ar)/2;
		if (check(mid)){
			ans=mid;
			ar=mid-1;
		}else{
			al=mid+1;
		} 
	}
	cout<<ans<<'\n';
	return 0;
}

/*
6 3
8  11 13 14 16 19
10 18 2  3  6  7

n1=1,n2=3 n2
8 11 13 14 16 7


*/