#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define INF (1 << 27)
#define EPS 0.00000000001
using namespace std;
int mNodes = 5000;
bool** graph;
int N, M;
int needed, built;
int result = 0;
queue < pair<int,int> > marked;
void read(){
    cin >> N >> M;
    graph = (bool**)malloc(sizeof(bool*)*N);
    for(int i=0;i<N;i++) graph[i] = (bool*)malloc(sizeof(bool)*M);
    for(int i=0;i<N;i++) for(int j=0;j<M;j++) graph[i][j] = false;
    cin >> needed >> built;
    for(int i=0;i<built;i++){
        pair <int,int> tmp;
        cin >> tmp.f >> tmp.s;
        tmp.f--, tmp.s--;
        marked.push(tmp);
        graph[tmp.f][tmp.s] = true;
    }
}
void printGraph(){
    for(int i=0;i<N;i++,cout<<endl)
        for(int j=0;j<M;j++)
                if(graph[i][j]) cout<<"x ";
                else cout<<"? ";
}
bool checkBounds(int x,int y){
    return (x >= 0 && x < N && y >= 0 && y < M);
}
void visitNeighbours(pair <int,int> tmp){
    int x = tmp.f, y = tmp.s;
    if(checkBounds(x,y+1) && !graph[x][y+1]){ built++; graph[x][y+1] = true; marked.push(mp(x,y+1)); }
    if(checkBounds(x+1,y) && !graph[x+1][y]){ built++; graph[x+1][y] = true; marked.push(mp(x+1,y)); }
    if(checkBounds(x,y-1) && !graph[x][y-1]){ built++; graph[x][y-1] = true; marked.push(mp(x,y-1)); }
    if(checkBounds(x-1,y) && !graph[x-1][y]){ built++; graph[x-1][y] = true; marked.push(mp(x-1,y)); }
}
void solve(){
    while(built<=needed){
     int qSize = marked.size();
        while(qSize > 0 ){
            visitNeighbours(marked.front());
            marked.pop();
            qSize--;
        }
        result++;
    }
    cout << result;
}

int main(){
    read();
    solve();
    //printGraph();
    return 0;
}