#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mx=510;
int n,K;
struct pt{
	int x,y;
}a[mx]; 
int dp[mx][mx];
bool cmp(pt A,pt B){
	return A.x<B.x;
}
signed main(){
	cin>>n>>K;
	for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y;
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++){
		for(int k=0;k<=K;k++) dp[i][k]=k+1;
	}
	
	for(int i=2;i<=n;i++){
		for(int j=i-1;j>=1;j--){
			if(a[j].y>a[i].y) continue;
			int d=a[i].x-a[j].x+a[i].y-a[j].y-1;
			for(int p=d;p<=K;p++) dp[i][p]=max(dp[i][p],dp[j][p-d]+d+1);
			
		}
	}
	
	int ans=0;
	for(int i=1;i<=n;i++) ans=max(ans,dp[i][K]);
	cout<<ans<<endl;
}