/*
problem: P8816 [CSP-J 2022] 上升点列
link: https://www.luogu.com.cn/problem/P8816
start: 2023/9/22 17:10
end: ?
*/
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = 1000 + 5; 


int n, k;
int dp[maxn][maxn];

struct Node {
	int x, y;
}a[maxn];

bool cmp(Node x, Node y) {
	if(x.x == y.x) 
		return x.y < y.y;

	return x.x < y.x;
} 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> k;
	for(int i = 1; i <= n; i++)  
		cin >> a[i].x >> a[i].y;

	sort(a + 1, a + 1 + n, cmp);
	
	int ans = 0;
	for(int i = 1; i <= n; i++) {
		dp[i][k] = 1;
		for(int j = 0; j <= k; j++) {
			for(int q = 1; q < i; q++) {
				if(a[i].x < a[q].y || a[i].y < a[q].y) continue;
				int dx = abs(a[i].x - a[q].x);
				int dy = abs(a[i].y - a[q].y);
				int d = dx + dy - 1;
				if(d + j > k) continue;
				dp[i][j] = max(dp[i][j], dp[q][j + d] + d + 1);
				ans = max(ans, dp[i][j] + j);
			}
		}
	}
	cout << ans << endl;
	return 0;
}