#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e3;
int n, k, dp[maxn][maxn];
struct point {
	int x, y;
	inline friend istream& operator >>(istream& cin, point& me) {return	cin >> me.x >> me.y;}
	inline bool operator>=(const point& a) {return x >= a.x && y >= a.y;}
	inline int disof(const point& a) { return x + y - a.x - a.y; }
}p[maxn];
signed main() {
	cin >> n >> k;
	for (int i = 1; i <= n; ++i) cin >> p[i];
	sort(p + 1, p + n + 1, [](const point& a, const point& b) {return a.x == b.x ? a.y <= b.y : a.x <= b.x; });
	for (int i = 0; i <= k; ++i)
		dp[1][i] = i + 1;
	for (int i = 2; i <= n; ++i)
		for (int j = 0; j <= k; ++j)
			for (int l = 1; l < i; ++l)
				if (int dis = p[i].disof(p[l]);p[i] >= p[l] && dis - 1 <= j)
					dp[i][j] = max(dp[i][j], dp[l][j - dis + 1] + dis);
	int ans = 0;
	for (int i = 1; i <= n; ++i) ans = max(ans, dp[i][k]);
	cout << ans;
}