#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N = 100003;

int in() {

	int k = 0, fh = 1; char c = getchar();

	for(; c < '0' || c > '9'; c = getchar())

		if (c == '-') fh = -1;

	for(; c >= '0' && c <= '9'; c = getchar())

		k = (k << 3) + (k << 1) + c - '0';

	return k * fh;

}

struct Point {

	int x, y, id;

	bool operator < (const Point &A) const {

		return x == A.x ? y < A.y : x < A.x;

	}

} P[N];

struct Bits {

	int mn, pos;

	void init() {mn = 0x7fffffff; pos = -1;}

} bit[N];

int tot;

struct Edge {

	int u, v, dis;

	bool operator < (const Edge &A) const {

		return dis < A.dis;

	}

} E[N << 2];

void add(int a, int b, int c) {E[++tot] = (Edge) {a, b, c};}

int n, fa[N], k;

int find(int x) {

	if (fa[x] == x) return x;

	fa[x] = find(fa[x]); return fa[x];

}

int dist(int x, int y) {

	return abs(P[x].x - P[y].x) + abs(P[x].y - P[y].y);

}

void update(int x, int num, int pos) {

	for(; x; x -= (x & (-x)))

		if (num < bit[x].mn)

			bit[x].mn = num, bit[x].pos = pos;

}

int m;

int query(int x) {

	int ans = 0x7fffffff, pos = -1;

	for(x; x <= m; x += (x & (-x)))

		if (bit[x].mn < ans)

			ans = bit[x].mn, pos = bit[x].pos;

	return pos;

}

int a[N], H[N], cnt;

int solve() {

	for(int change = 0; change < 4; ++change) {

		if (change == 1 || change == 3)

			for(int i = 1; i <= n; ++i) swap(P[i].x, P[i].y);

		else if (change == 2)

			for(int i = 1; i <= n; ++i) P[i].x = -P[i].x;

		sort(P + 1, P + n + 1);

		for(int i = 1; i <= n; ++i)

			a[i] = H[i] = P[i].y - P[i].x;

		cnt = n;

		sort(H + 1, H + cnt + 1);

		cnt = unique(H + 1, H + cnt + 1) - H;

		for(int i = 1; i <= cnt; ++i) bit[i].init();

		int pos, tmp; m = cnt;

		for(int i = n; i > 0; --i) {

			pos = lower_bound(H + 1, H + cnt, a[i]) - H;

			tmp = query(pos);

			if (tmp != -1)

				add(P[i].id, P[tmp].id, dist(i, tmp));

			update(pos, P[i].x + P[i].y, i);

		}

	}

	sort(E + 1, E + tot + 1);

	cnt = n - k;

	for(int i = 1; i <= n; ++i) fa[i] = i;

	int u, v;

	for(int i = 1; i <= tot; ++i) {

		u = find(E[i].u); v = find(E[i].v);

		if (u != v) {

			--cnt;

			fa[u] = v;

			if (cnt == 0) return E[i].dis;

		}

	}

}

int main() {

	while (~scanf("%d%d", &n, &k)) {

		tot = 0;

		for(int i = 1; i <= n; ++i) {

			P[i].x = in(); P[i].y = in();

			P[i].id = i;

		}

		printf("%d\n", solve());

	}

	return 0;

}