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

int f[605][105];

struct Point {
	int x, y;

	bool operator<(const Point &point) const {
		if (x - point.x)
			return x < point.x;
		else
			return y < point.y;
	}
} point[505];

int dis(const Point &a, const Point &b) {
	return abs(a.x - b.x) + abs(a.y - b.y) - 1;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	memset(f, -0x7f, sizeof(f));
	int n, d;
	cin >> n >> d;
	for (int i = 1; i <= n; i++)
		cin >> point[i].x >> point[i].y;
	sort(point + 1, point + n + 1);
	int ans = INT_MIN;
	for (int i = 1; i <= n; i++)
		for (int j = 0; j <= d; j++)
			f[i][j] = 1 + j;
	for (int i = 2; i <= n; i++) {
		for (int j = 0; j <= d; j++)
			for (int k = 1; k < i; k++)
				if (j >= dis(point[i], point[k]))
					f[i][j] = max(f[i][j], f[k][j - dis(point[i], point[k])] + dis(point[i], point[k]) + 1);
		ans = max(ans, f[i][d]);
	}
	cout << ans << '\n';
	return 0;
}