#include<cstdio>
using namespace std;
struct p{
	int x,y;
}a[505];
int cmp(p a,p b){
	if(a.x!=b.x) return a.x<b.x;
	else return a.y<b.y;
}
int d[505][105]/*i到j的欧几里得距离*/,f[505][105]/*dpLIS*/;
int main(){
	freopen("point.in","r",stdin);
	freopen("point.out","w",stdout);
	int n,m;
	scanf("%d%d",&n,&m);
	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 j=1;j<i;j++){
			if(a[i].x<a[j].x||a[i].y<a[j].y) d[i][j]=-1;
			else d[i][j]=a[i].x-a[j].x+a[i].y-a[j].y;
		}
	}
	for(int i=1;i<=n;i++){
		for(int k=0;k<=m;k++){
			f[i][k]=k+1;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<i;j++){
			if(d[i][j]==-1) continue;
			for(int k=0;k<=m;k++){
				if(d[i][j]==1) f[i][k]=max(f[i][k],f[j][k]+1);
				else if(k>=d[i][j]-1){
					f[i][k]=max(f[i][k],f[j][k-d[i][j]+1]+d[i][j]);
				}
			}
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++) ans=max(ans,f[i][m]);
	cout<<ans;
	return 0;
}