#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.tie(0); ios::sync_with_stdio(0);
    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 = log2(N+M);
    int lastn = n;
    while (true) {
        int csoportok;
        getGroups(csoportok, n);
        if (csoportok > K) {
            minn = n;
            n = (n+maxn)/2;
        }
        else if (csoportok <= K) {
            maxn = n;
            n = (n+minn)/2;
        }
        if (n == lastn) break;
        lastn = n;
    }
    if (csoportok <= K) {
        cout << n;
    }
    else {
        while (csoportok > K) {
            n++;
            getGroups(csoportok, n);
        }
        cout << n;
    }
}