#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int dist (pair<int,int> a,pair<int,int> b) {
    return abs(a.first - b.first) + abs(a.second - b.second);
}
int main() {
    int n,k;
    cin >> n >> k;
    vector<pair<int,int>> v(n);
    for (int i = 0;i < n;i++) {
        cin >> v[i].first >> v[i].second;
    }
    int arr[n]={0,};
    for (int i = n-k;i < n;i++) {
        arr[i] = 1;
        
    }
   
    int min_val = 200001;
    

    do {
     //   cout << 0;
        int max_val = 0;
        for (int i = 0;i < n;i++) {
          //  cout << arr[i] << " ";
            if (arr[i] == 0) {
                int min_value = 200001;
                for (int j = 0;j < n;j++) {
                    if (arr[j] == 1) {
                        min_value = min(min_value,dist(v[i],v[j]));
                    //    cout << min_value << " " << j<<" ";
                    }
                }
                max_val = max(max_val,min_value);
                //cout << max_val << " ";
            }    
        }
        min_val = min(min_val,max_val);
    }while(next_permutation(arr,arr+n));

    cout << min_val;
    return 0;
}