#include<bits/stdc++.h> 
using namespace std;
const int N=20005;
int n,k,ans=0x3f,d1,d2=0x3f,d3,d4=0x3f;
struct node{
	int x,y;
}a[N];
void baoli(int u,int h){
	if(u<=1+n&&h==k){
		ans=min(ans,max(d1-d2,d3-d4));
		return;
	}
	if(u==1+n) return;
	int o=d1,p=d2,w=d3,l=d4;
	d1=max(d1,a[u].x);
	d2=min(d2,a[u].x);
	d3=max(d3,a[u].y);
	d4=min(d4,a[u].y);
	baoli(u+1,h+1);
	d1=o,d2=p,d3=w,d4=l;
	baoli(u+1,h);
	return;
}
int main(){
	freopen("expert.in","r",stdin);
	freopen("expert.out","w",stdout);
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&a[i].x,&a[i].y);
	}
	baoli(1,0);
	printf("%d",ans);
	return 0;
}