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

n, m = map(int, input().split())
house = [(x + y, x - y) for x,y in [map(int, input().split()) for _ in [0]*n]]

def calc_dist_max(bit):
	if(bit == 0):
		return 0
	x_max, x_min, y_max, y_min = -INF, INF, -INF, INF
	i = 0
	for i, (x,y) in enumerate(house):
		if not((bit >> i) & 1):
			continue
		if(x_max < x):
			x_max = x
		if(x_min > x):
			x_min = x
		if(y_max < y):
			y_max = y
		if(y_min > y):
			y_min = y
	return max(x_max - x_min, y_max - y_min)

req_dist = [calc_dist_max(bit) for bit in range(1 << n)]
dp = [[INF]*(1 << n) for _ in [0]*(m + 1)]
dp[0][0] = 0
for k in range(m):
	for bit in range(1 << n):
		bit2 = rev = ((1 << n) - 1) - bit
		while(bit2):
			d = max(dp[k][bit], req_dist[bit2])
			if(dp[k + 1][bit | bit2] > d):
				dp[k + 1][bit | bit2] = d
			bit2 = (bit2 - 1) & rev

ans = dp[m][-1]
print(ans)