#include <bits/stdc++.h>
using namespace std;

struct pt {
	int x, y;
} p[510];
int n, k, fx[510], fy[510];
int ans = -1;
int maxn = 0;

int zc(int x, int y) {
	fy[1] = p[x].y;
	fx[1] = p[x].x;
	int len = 1;
	for (int i = x + 1; i <= y; i++) {
		if (p[i].y > p[y].y || p[i].y < p[x].y)
			continue;
		if (p[i].y >= fy[len])
			fy[++len] = p[i].y, fx[len] = p[i].x;
		int j = upper_bound(fy + 1, fy + len + 1, p[i].y) - fy;
		fy[j] = p[i].y;
		fx[j] = p[i].x;
	}
	return len - 1;
}

int di(int x) {
	if (x < 0)
		return -x;
	return x;
}

int dis(int a, int b, int c, int d) {
	return di(a - c) + di(b - d);
}

bool cmp(pt x, pt y) {
	if (x.x != y.x)
		return x.x < y.x;
	return x.y < y.y;
}

int main() {
	freopen("csp2022pj_point.in", "r", stdin);
	freopen("csp2022pj_point.out", "w", stdout);
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> p[i].x >> p[i].y;
	}
	sort(p + 1, p + n + 1, cmp);
	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
			if (p[i].y > p[j].y)
				continue;
			if (j != i) {
				int m = zc(i, j);
				int dist = dis(p[i].x, p[i].y, p[j].x, p[j].y);
				if (dist - m > k)
					continue;
				if (ans < dist) {
					ans = dist;
					maxn = dist - m;
				}
				if (ans == dist) {
					maxn = max(maxn, dist - m);
				}
			}
		}
	}
	cout << ans + k - maxn + 1  << endl;
	return 0;
}