#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 = 0;

    for (int i = 0; i < n; i++)
    {
        if(volt[i]) continue;
        cnt++;
        bfs(i, 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]) 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 = 0, right = 1000001, mid;
    //cout << "----\n";
    while(left <= right)
    {
        
        mid = left+(right-left)/2;
        //cout << left << " " << mid << " " << right << "\n";

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

    cout << (mid) << "\n";

    return 0;
}