#include <stdio.h>
#include <stdlib.h>
int main()
{
int a,b,c[10000][2]={},i,k,j,l,t=-1,max=-1,x,z,y;
scanf("%d %d",&a,&b);
for(i=0;i<a;i++)
scanf("%d %d",&c[i][0],&c[i][1]);
for(k=0;k<a;k++) {
t=0;
for(i=0;i<a;i++) {
if(i==k)
continue;
if(b>=2)
{
t=0;
for(j=0;j<a;j++) {
if(j == k || j == i)
continue;
if(b==3)
{
t=0;
for(l=0;l<a;l++) {
if(l == k || l == j || l == i)
continue;
x = abs(c[k][0] - c[l][0]) + abs(c[k][1] - c[l][1]);
y = abs(c[i][0] - c[l][0]) + abs(c[i][1] - c[l][1]);
z = abs(c[j][0] - c[l][0]) + abs(c[j][1] - c[l][1]);
if(y < x && y < z && t < y)
t=y;
else if(x < z && x < y && t < x)
t=x;
else if(t < z && z < x && z < y)
t=z;
}
}
else {
x = abs(c[k][0] - c[j][0]) + abs(c[k][1] - c[j][1]);
y = abs(c[i][0] - c[j][0]) + abs(c[i][1] - c[j][1]);
if(y < x && t < y)
t=y;
else if(x < y && t < y)
t=x;
}
}
}
else {
x = abs(c[k][0] - c[i][0]) + abs(c[k][1] - c[i][1]);
if(t < x) {
t=x;
}
}
}
if(t < max || max == -1)
max = t;
}
printf("%d",max);
return 0;
}