import heapq
N,K = map(int,input().split())
sx,sy,gx,gy = map(int,input().split())
INFTY = 10**6
A = [(sx,sy)]+[tuple(map(int,input().split())) for _ in range(N)]+[(gx,gy)]
low = 0
high = INFTY
while high-low>1:
    mid = (high+low)//2
    G = {i:{} for i in range(N+2)}
    for i in range(N+1):
        xi,yi = A[i]
        for j in range(i+1,N+2):
            xj,yj = A[j]
            d = abs(xj-xi)+abs(yj-yi)
            if d<=mid:
                G[i][j] = 0
                G[j][i] = 0
            else:
                G[i][j] = (d+mid-1)//mid-1
                G[j][i] = (d+mid-1)//mid-1
    dist = [INFTY]*(N+2)
    dist[0] = 0
    visited = [False]*(N+2)
    heap = [(0,0)]
    while heap:
        d,i = heapq.heappop(heap)
        if d>dist[i]:continue
        visited[i] = True
        for j in G[i]:
            if visited[j]:continue
            d1 = G[i][j]
            if dist[j]>d+d1:
                dist[j] = d+d1
                heapq.heappush(heap,(d+d1,j))
    if dist[N+1]<=K:
        high = mid
    else:
        low = mid
print(high)