#include <algorithm>
#include <iostream>
#include <vector>
#include <tuple>

using namespace std;

struct person {
    int x, y;
};

vector<int> parent;
vector<int> sz;
int components;

int find(int const x) {
    if (parent[x] == -1)
        return x;

    return parent[x] = find(parent[x]);
}

void merge(int const x, int const y) {
    int px = find(x);
    int py = find(y);

    if (px == py)
        return;

    components--;

    if (sz[px] < sz[py])
        swap(px, py);

    parent[py] = px;
    sz[px] += sz[py];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, h, k;
    cin >> n >> m >> h >> k;

    vector<person> people(h);
    for (person& p : people)
        cin >> p.x >> p.y;

    vector<pair<int, pair<int, int>>> distances;

    for (int i = 0; i < h - 1; i++) {
        for (int j = i + 1; j < h; j++) {
            distances.push_back({ abs(people[i].x - people[j].x) + abs(people[i].y - people[j].y), { i, j } });
        }
    }

    sort(distances.begin(), distances.end());

    parent.assign(h, -1);
    sz.assign(h, 1);
    components = h;

    if (components <= k) {
        cout << "0\n";
        return 0;
    }

    for (auto dist : distances) {
        int const d = dist.first;
        int const i = dist.second.first;
        int const j = dist.second.second;

        merge(i, j);

        if (components <= k) {
            cout << d << "\n";
            return 0;
        }
    }
}