N, M, H, K = map(int, input().split())
hs = [tuple(map(int, input().split())) for _ in range(H)]

# counting sort of edges, we can afford O(n^2)
edges = [[] for _ in range(20000)]
for i in range(H):
    for j in range(i + 1, H):
        dist = abs(hs[i][0] - hs[j][0]) + abs(hs[i][1] - hs[j][1])
        edges[dist].append((i, j))

# https://en.wikipedia.org/wiki/Disjoint-set_data_structure
par = list(range(H))
rank = [0] * H
count = H

def find(a):
    while par[a] != a:
        # path halving
        par[a] = par[par[a]]
        a = par[a]
    return a

def union(a, b):
    global count
    a = find(a)
    b = find(b)
    if a == b:
        return
    count -= 1
    # merge by rank
    if rank[a] == rank[b]:
        par[b] = a
        rank[a] += 1
    elif rank[a] > rank[b]:
        par[b] = a
    else:
        par[a] = b

for dist, es in enumerate(edges):
    for a, b in es:
        union(a, b)
    if count <= K:
        print(dist)
        exit()