#include <bits/stdc++.h>

using namespace std;

const int N = 510, K = 110;

int dp[N][K], n, k, ans;

struct point {
	int x, y;
}points[N];

bool cmp (point a, point b) {
	if (a.x == b.x) return a.y < b.y;
	return a.x < b.x;
}

int main () {
	freopen("csp2022pj_point.in", "r", stdin);
	freopen("csp2022pj_point.out", "w", stdout);
	scanf("%d%d", &n, &k);
	for (int i = 1;i <= n;i++) scanf("%d%d", &points[i].x, &points[i].y);
	sort(points + 1, points + 1 + n, cmp);
	for (int i = 1;i <= n;i++) {
		int nx = points[i].x, ny = points[i].y;
		for (int j = 0;j <= k;j++) {
			int cnt = 0;
			for (int z = 1;z < i;z++) {
				int x = points[z].x, y = points[z].y, g = abs(nx - x) + abs(ny - y) - 1;
				if (y > ny) continue;
				if (g <= j) cnt = max(cnt, dp[z][j - g] + g);
			}
			dp[i][j] = cnt + 1;
			if (j) dp[i][j] = max(dp[i][j], dp[i][j - 1]);
		}
	}
	for (int i = 1;i <= n;i++) for (int j = 0;j <= k;j++) ans = max(ans, dp[i][j] + k - j);
	printf("%d\n", ans);
	return 0;
}