#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    int w, l, n, b, s = 0;
    cin >> w >> l >> n >> b;
    bool visited[1001][1001];
    for (int i = 0; i < w; i++) {
        for (int j = 0; j < l; j++) {
            visited[i][j] = false;
        }
    }
    int di[] = { 1, -1, 0, 0 };
    int dj[] = { 0, 0, 1, -1 };
    queue<vector<pair<int, int>>> q;
    vector<pair<int, int>> v;
    for (int i = 0; i < b; i++) {
        int a, b2;
        cin >> a >> b2;
        v.push_back(make_pair(a - 1, b2 - 1));
        visited[a-1][b2-1] = true;
    }
    q.push(v);
    int b2 = b;
    while (!q.empty()) {
        vector<pair<int, int>> k, v2;
        k = q.front();
        q.pop();
        for (int i = 0; i < k.size(); i++) {
            for (int j = 0; j < 4; j++) {
                int c, p;
                c = k[i].first + di[j];
                p = k[i].second + dj[j];
                if (c >= 0 and c < w and p >= 0 and p < l and !visited[c][p]) {
                    visited[c][p] = true;
                    v2.push_back(make_pair(c, p));
                    b2++;
                }
            }
        }
        q.push(v2);
        s++;
        if (b2 >= n) {
            cout << s << endl;
            return 0;
        }

    }


    return 0;
}