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

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

int cnt;
void bfs(int c, int &n, int &cl, int &k, vector<bool> &volt, vector<pair<int, int>> &pontok);

bool megold(int n, int cl, int &k, vector<bool> &volt, vector<pair<int, int>> &pontok)
{
    fill(volt.begin(), volt.end(), false);
    
    cnt = 1;

    for (size_t i = 0; i < n; i++)
    {
        if(volt[i]) continue;
        cnt++;
        bfs(0, n, cl, k, volt, pontok);
    }

    return cnt <= k;
}

void bfs(int c, int &n, int &cl, int &k, vector<bool> &volt, vector<pair<int, int>> &pontok)
{
    
    volt[c] = true;
    for(int i = 0; i < n; i++)
    {
        if(volt[i] || i == c) continue;
        if(abs(pontok.at(c).first-pontok.at(i).first)+abs(pontok.at(c).second-pontok.at(i).second) <= cl)
        {
            bfs(i, n, cl, k, volt, pontok);
            continue;
        }
    }
}

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 = 1, right = 1000001, mid;
    
    while(left < right)
    {
        mid = left+(right-left)/2;

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

    cout << (right-1) << "\n";

    return 0;
}