#include <cstdio>
#define min(__a, __b) [&](int _a, int _b) {return _a < _b ? _a : _b;} ((__a), (__b))
#define max(__a, __b) [&](int _a, int _b) {return _a > _b ? _a : _b;} ((__a), (__b))

const int MAXN = 1e5 + 10;
const int INF = 0x7fffffff;

struct ITEM {
  int x, y;
} a[MAXN];

int n, k;
int b[MAXN];
int ans = INF;

void work() {
  int xmin = INF, xmax = -INF, ymin = INF, ymax = -INF;
  for (int i = 1; i <= k; ++i) {
    xmin = min(xmin, a[b[i]].x);
    xmax = max(xmax, a[b[i]].x);
    ymin = min(ymin, a[b[i]].y);
    ymax = max(ymax, a[b[i]].y);
  }
  int c = max(xmax - xmin, ymax - ymin);
  ans = min(ans, c);
}

void dfs(int pos) {
  if (pos == k + 1) {
    work();
    return ;
  }
  for (int i = b[pos - 1] + 1; i <= n; ++i) {
    b[pos] = i;
    dfs(pos + 1);
  }
}

int main() {
  freopen("expert.in", "r", stdin);
  freopen("expert.out", "w", stdout);
  scanf("%d %d", &n, &k);
  for (int i = 1; i <= n; ++i) {
    scanf("%d %d", &a[i].x, &a[i].y);
  }
  dfs(1);
  printf("%d\n", ans);
  return 0;
}