#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;
#define fastio cin.tie(0)->sync_with_stdio(0)

using ll = long long;
using matrix = vector<vector<ll>>;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vpii = vector<pii>;
using vb = vector<bool>;

int n, k;
vi x, y, xs, ys;
const int INF = 1e9;

int calc(int p1, int p2, int p3) {
    int ans = 0;
    for(int i=0; i<n; ++i) {
        ans = max(ans, min({abs(x[i]-x[p1]) + abs(y[i]-y[p1]), abs(x[i]-x[p2]) + abs(y[i]-y[p2]), abs(x[i]-x[p3]) + abs(y[i]-y[p3])}));
    }
    return ans;
}

void solve() {
    cin >> n >> k;
    x = vi(n), y = vi(n);
    for(int i=0; i<n; ++i) cin >> x[i] >> y[i];
    
    int ans = INF;
    if(k==1) {
        for(int i=0; i<n; ++i) ans = min(ans, calc(i, i, i));
    }
    else if(k==2) {
        for(int i=0; i<n; ++i) {
            for(int j=i; j<n; ++j) {
                ans = min(ans, calc(i, j,j));
            }
        }
    }   
    else if(k==3) {
        for(int i=0; i<n; ++i) {
            for(int j=i; j<n; ++j) {
                for(int k=j; k<n; ++k) {
                    ans = min(ans, calc(i, j,k));
                }
            }
        }
    }
    cout << ans;
}

int main() {
    fastio;
    solve();
    return 0;
}