#include<bits/stdc++.h>
using namespace std;
const int N = 505;
int n, k, a[N], dp[N], sum[N], use[N];
struct Point {
	int x, y;
}p[N];
bool cmp(Point xx, Point yy) {
	if(xx.x != yy.x)return xx.x < yy.x;
	return xx.y < yy.y;
}
int calc(int i, int j) {
	return abs(p[j].x - p[i].x) + abs(p[j].y - p[i].y) - 1;
}
int main() {
	freopen("point.in", "r", stdin);
	freopen("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);
	if(k == 0) { // 40pts
		dp[1] = 1;
		for(int i = 2; i <= n; ++i) {
			dp[i] = 1;
			for(int j = 1; j < i; ++j) {
				if((p[i].x == p[j].x && p[i].y == p[j].y + 1)) dp[i] = max(dp[i], dp[j] + 1);
				if(p[i].y == p[j].y && p[i].x == p[j].x + 1) dp[i] = max(dp[i], dp[j] + 1); 
			}
		}
		int ans = 0;
		for(int i = 1; i <= n; ++i) {
			ans = max(ans, dp[i]);
		}
		cout << ans;
		return 0;
	}
	sum[1] = 1; //Maybe 100pts
	for(int i = 2; i <= n; ++i) {
		sum[i] = 1;
		use[i] = 0;
		for(int j = 1; j < i; ++j) {
			if(p[i].x >= p[j].x && p[i].y >= p[j].y) {
				int now = sum[j] + calc(i, j) + 1;
				if(now > sum[i]) {
					sum[i] = now;
					use[i] = use[j] + calc(i, j);
				}
				if(sum[i] == now) {
					use[i] = min(use[i], use[j] + calc(i, j));
				}
			} 
		}
	}
	int ans = 0;
	for(int i = 1; i <= n; ++i) {
		if(use[i] <= k) {
			ans = max(ans, sum[i] + k - use[i]);
		}
	}
	cout << ans;
	return 0;
}

思路是按 $x,y$ 排序后，选出来的序列在这个序列上单调，然后记 $sum_i$ 为以 $i$ 结尾的最大答案，$use_i$ 是在 $sum_i$ 的基础上最少的花费，答案是 $\max_{use_i\le k} sum_i+k-use_i$