#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, vector<vector<int>>& graph) {
    been[loc] = true;
    for (size_t i = 0; i < hirek.size(); i++)
    {
        if (i == loc || been[i]) continue;
        if (graph[i][loc] <= d) dfs(d, i, graph);
    }
}

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

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});
    }
    vector<vector<int>> graph (H, vector<int>(H));
    for (size_t i = 0; i < H; i++)
    {
        for (size_t k = 0; k < H; k++)
        {
            graph[i][k] = graph[k][i] = abs(hirek[i].first - hirek[k].first) + abs(hirek[k].second - hirek[i].second);
        }
    }
    
    int csoportok, minn = 0, maxn = N+M, n = log2(N+M);
    int lastn = n;
    while (true) {
        int csoportok;
        getGroups(csoportok, n, graph);
        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, graph);
        }
        cout << n;
    }
}