#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

int tav(pii a, pii b){
    return abs(a.first - b.first) + abs(a.second - b.second);
}

int h;
vector<vector<pii>> graf;
vector<int> volt;
int ido = 0;

void dfs(int akt, int& l){
    volt[akt] = ido;
    for(auto kov : graf[akt]){
        if(kov.first > l) break;
        if(volt[kov.second] >= ido) continue;
        dfs(kov.second, l);
    }
}


int csoport_db(int l){
    int ki = 0;
    ido++;
    for(int i = 0; i < h; i++){
        if(volt[i] < ido){
            ki++;
            dfs(i, l);
        }
    }
    return ki;
}


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, k;
    cin >> n >> m >> h >> k;
    // tav, kovi
    graf.assign(h, vector<pii>());
    volt.assign(h, 0);
    vector<pii> hely(h);
    for(int i = 0; i < h; i++){
        cin >> hely[i].first >> hely[i].second;
    }
    int t;
    for(int i = 0; i < h; i++){
        for(int j = i+1; j < h; j++){
            t = tav(hely[i], hely[j]);
            graf[i].push_back({t, j});
            graf[j].push_back({t, i});
        }
    }
    for(int i = 0; i < h; i++){
        sort(graf[i].begin(), graf[i].end());
    }

    int ki = -1;
    int l = 0, r = 20200;
    int mid;
    while(l <= r){
        mid = (l+r) / 2;
        if(csoport_db(mid) <= k){
            r = mid - 1;
            ki = mid;
        }
        else{
            l = mid + 1;
        }
    }

    cout << ki << "\n";
}