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

#define GOTTAGOFAST cin.tie(0); ios::sync_with_stdio(0);

int cnt;

inline bool megold(vector<vector<int>> &graf, int cl, int &k, vector<bool> &volt)
{
    fill(volt.begin(), volt.end(), false);
    
    cnt = 0;
    queue<int> next;

    for(int i = 0; i < graf.size(); ++i)
    {
        if(volt[i]) continue;

        cnt++;

        next.push(i);
        while(!next.empty())
        {
            volt.at(next.front()) = true;
            for(int j = 0; j < graf.size(); ++j)
            {
                if(volt[j] || graf.at(next.front()).at(j) == -1) continue;

                if(graf.at(next.front()).at(j) < cl)
                {
                    next.push(j);
                }
            }
            next.pop();
        }
    }

    return cnt <= k;
}

int main()
{

    GOTTAGOFAST

    int x, y, n, k;
    cin >> x >> y >> n >> k;

    vector<vector<int>> graf(n, vector<int>(n, -1));
    vector<pair<int, int>> pontok(n);
    vector<bool> volt(n);
    int a, b;
    for (size_t i = 0; i < n; i++)
    {
        cin >> a >> b;
        pontok.at(i) = {a, b};
    }

    int left = INT_MAX, right = -1, mid;

    for (size_t i = 0; i < n; i++)
    {
        for (size_t j = 0; j < n; j++)
        {
            if(i == j || graf.at(i).at(j) != -1) continue;
            graf.at(i).at(j) = abs(pontok.at(i).first-pontok.at(j).first)+abs(pontok.at(i).second-pontok.at(j).second);
            left = min(graf.at(i).at(j), left);
            right = max(graf.at(i).at(j), right);
        }
        
    }
    
    while(left < right)
    {
        mid = left+(right-left)/2;

        if(megold(graf, mid, k, volt))
        {
            right = mid-1;
        }
        else
        {
            left = mid+1;
        }
    }

    cout << right << "\n";

    return 0;
}