import sys
input = sys.stdin.readline
INF = 10 ** 18

N, K = map(int, input().split())
P = [list(map(int, input().split())) for _ in [0] * N]

def calc(bit):
	x = [];	y = []
	i = 0
	while(bit):
		if(bit & 1):
			x.append((P[i][0] + P[i][1], i))
			y.append((P[i][0] - P[i][1], i))
		bit >>= 1
		i += 1
	if(len(x) == 0):
		return 0
	x.sort();	y.sort()
	p = x[0][1];	q = x[-1][1]
	if(y[-1][0] - y[0][0] > x[-1][0] - x[0][0]):
		p = y[0][1];	q = y[-1][1]
	return (abs(P[p][0] - P[q][0]) + abs(P[p][1] - P[q][1])) // 2

need = [calc(bit) for bit in range(1 << N)]
dp = [[INF] * (1 << N) for _ in [0] * (K + 1)]
dp[0][0] = 0
for k in range(K):
	for bit in range(1 << N):
		bit2 = rev = ((1 << N) - 1) - bit
		while(bit2):
			d = max(dp[k][bit], need[bit2])
			if(dp[k + 1][bit|bit2] > d):
				dp[k + 1][bit|bit2] = d
			bit2 = (bit2 - 1) & rev

print(dp[K][-1])