#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int maxn = 1e6+10;
int INF = 0x3f3f3f3f;
int n, k;
struct Point{
    int x, y;
    int id;
}p[maxn];
struct BIT{
    int min_val, pos;
    void init(){
        min_val = INF;
        pos = -1;
    }
}bit[maxn];
struct Edge{
    int u, v, d;
}edge[maxn<<2];
bool cmp_edge(Edge a,Edge b){
    return a.d<b.d;
}
int tot;
int fa[maxn];
int find_fa(int x){
    int a = x;
    while(x!=fa[x]) x = fa[x];
    while(a!=fa[a]){
        int z = a;
        a = fa[a];
        fa[z] = x;
    }
    return x;
}
void add_edge(int u, int v, int w){
    edge[tot].v = v;
    edge[tot].u = u;
    edge[tot++].d = w;
}
int low_bit(int x){
    return x&(-x);
}
//i表示从[1, i]区间开始的
void update(int i, int val, int pos){
    while(i>0){
        if(val<bit[i].min_val){
            bit[i].min_val = val;
            bit[i].pos = pos;
        }
        i -= low_bit(i);
    }
}
int ask(int i, int m){
    int min_val = INF, pos = -1;
    while(i<=m){
        if(bit[i].min_val<min_val){
            min_val = bit[i].min_val;
            pos = bit[i].pos;
        }
        i += low_bit(i);
    }
    return pos;
}
bool cmp(Point a, Point b){
    if(a.x!=b.x) return a.x<b.x;
    else return a.y<b.y;
}
bool cmpedge(Edge a, Edge b){
    return a.d<b.d;
}
int dis(Point a, Point b){
    return abs(a.x-b.x)+abs(a.y-b.y);
}
//数组开在里面会爆栈
int a[maxn], b[maxn];
void Manha_minimum_spanning_tree(int n, int k){
    int tot = 0;
    for(int dir=0; dir<4; dir++){
        if(dir == 1|| dir == 3){
            for(int i=0; i<n; i++){
                swap(p[i].x, p[i].y);
            }
        }
        else if(dir == 2){
            for(int i=0; i<n; i++){
                p[i].x = -p[i].x;
            }
        }
        sort(p, p+n, cmp);
        for(int i=0; i<n; i++){
            a[i] = b[i] = p[i].y-p[i].x;
        }
        sort(b, b+n);
        int m = unique(b, b+n)-b;
        for(int i=1; i<=m; i++){
            bit[i].init();
        }
        for(int i=n-1; i>=0; i--){
            int pos = lower_bound(b, b+m, a[i]) - b+1;//坐标从1开始
            int ans = ask(pos, m);
            if(ans != -1){
                add_edge(p[i].id, p[ans].id, dis(p[i], p[ans]));
            }
            update(pos, p[i].x+p[i].y, i);
        }
    }
}
int solve(int k){
    Manha_minimum_spanning_tree(n, k);
    for(int i=0; i<=n; i++)fa[i] = i;
    sort(edge, edge+tot, cmpedge);
    for(int i=0; i<tot; i++){
        int u = edge[i].u;
        int v = edge[i].v;
        int d = edge[i].d;
        int fau = find_fa(u);
        int fav = find_fa(v);
        if(fau!=fav){
            fa[fau] = fav;
            k--;
            if(k ==0 ) return edge[i].d;
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    while(~scanf("%d%d", &n, &k)&&n){
        for(int i=0; i<n; i++){
            scanf("%d%d", &p[i].x, &p[i].y);
            p[i].id = i;
        }
        printf("%d\n", solve(n-k));
    }
    return 0;
}