#include <bits/stdc++.h>
#define int long long
using namespace std;
struct node{
	int x,y;
	friend bool operator<(node a,node b){
		if(a.y==b.y)return a.x<b.x;
		else return a.y<b.y;
	}
}p[505];
int f[505][105],n,k,res;
int jl(int a,int b){
	return p[b].x-p[a].x+p[b].y-p[a].y-1;
}
signed main(){
	freopen("csp2022pj_point.in","r",stdin);
	freopen("csp2022pj_point.out","w",stdout);
	cin>>n>>k;
	for(int i=1;i<=n;i++)scanf("%lld%lld",&p[i].x,&p[i].y);
	sort(p+1,p+n+1);
	for(int i=1;i<=n;i++){
		f[i][0]=1;
		for(int j=0;j<=k;j++){
			for(int l=1;l<i;l++){
				if(p[l].x<=p[i].x){
					if(j>=jl(l,i))f[i][j]=max(f[i][j],f[l][j-jl(l,i)]+jl(l,i)+1);
				}
			}
			res=max(res,f[i][j]+k-j);
		}
	}
	cout<<res;
	return 0;
}