#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k,d,m;
pair<int,int> a[505];
int dp[505][105];
signed main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i].first>>a[i].second;
	}
	sort(a+1,a+1+n);
	for(int i=1;i<=n;i++){
		for(int p=1;p<=k;p++){
			dp[i][p]=p+1;
			for(int j=1;j<=n;j++){
				d=a[i].first-a[j].first+a[i].second-a[j].second-1;
				if(d<=p&&a[i].first>=a[j].first&&a[i].second>=a[j].second)dp[i][p]=max(dp[i][p],dp[j][p-d]+d+1);
			}
		}
		m=max(m,dp[i][k]);
	}
	cout<<m;
	return 0;
}