from heapq import heappop, heappush import sys input = sys.stdin.readline INF = 10 ** 18 C = 10 ** 7 def main(): N, K = map(int, input().split()) sx, sy, gx, gy = map(int, input().split()) X, Y = [sx, gx], [sy, gy] for _ in range(N): x, y = map(int, input().split()) X.append(x) Y.append(y) def solve(P): hq = [] heappush(hq, 0) dist = [INF] * (N + 2) dist[0] = 0 while hq: now = heappop(hq) % C for i in range(N + 2): if now == i: continue ndist = dist[now] + (abs(X[i] - X[now]) + abs(Y[i] - Y[now]) - 1) // P if dist[i] > ndist: dist[i] = ndist heappush(hq, ndist * C + i) return dist[1] <= K lo = 0 hi = 2 * 10 ** 5 + 10 while hi - lo > 1: p = (hi + lo) // 2 if solve(p): hi = p else: lo = p print(hi) if __name__ == "__main__": main()