#include <bits/stdc++.h>
using namespace std;

int N, M, H, K;
vector<bool> been;
vector<pair<int, int>> hirek;

void dfs(int& d, int loc) {
    been[loc] = true;
    for (size_t i = 0; i < hirek.size(); i++)
    {
        if (i == loc || been[i]) continue;
        if (abs(hirek[i].first - hirek[loc].first) + abs(hirek[i].second - hirek[loc].second) <= d) dfs(d, i);
    }
}

void getGroups(int& csoportok, int n) {
    csoportok = 0;
    been.assign(H, false);
    for (size_t i = 0; i < H; i++)
    {
        if (been[i]) continue;
        csoportok++;
        dfs(n, i);
    }
}

int main() {
    cin >> N >> M >> H >> K;
    int x, y;
    for (size_t i = 0; i < H; i++)
    {
        cin >> x >> y;
        hirek.push_back({x, y});
    }
    int csoportok, minn = 0, maxn = N+M, n = (N+M)/2;
    int lastn = n;
    while (true) {
        int csoportok;
        getGroups(csoportok, n);
        if (csoportok > K) {
            minn = n;
            n = (n+maxn)/2;
            if (n == lastn) {
                for (size_t i = n; i < N+M; i++)
                {
                    getGroups(csoportok, i);
                    if (csoportok < K) {
                        cout << i;
                        return 0;
                    }
                }
            }
            
            lastn = n;
        }
        else if (csoportok < K) {
            maxn = n;
            n = (n+minn)/2;
            if (n == lastn) {
                cout << n;
                return 0;
            }
            lastn = n;
        }
        else {
            cout << n << "\n";
            return 0;
        }
    }
}