2023tyoi0427

#include <iostream>
#include <algorithm>
#include <iomanip>
#include <vector>
using namespace std;

struct point{
	int x,y;
};
point p[600];
int dp[600][105];

bool cmp(point a,point b){
	if(a.x!=b.x) return a.x<b.x;
	return a.y<b.y;
}

int main(){
	freopen("point.in","r",stdin);
	freopen("point.out","w",stdout);
	int n,k;
	int ans=k+1;
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>p[i].x>>p[i].y;
	sort(p+1,p+n+1,cmp);
	int use=0,as=0;
	for(int i=1;i<=n;i++) {
		for(int j=0;j<=k;j++) dp[i][j]=1+j;
	}
	for(int i=1;i<=n;i++){
		for(int t=0;t<=k;t++){
			for(int j=i+1;j<=n;j++){
				if(i==j)continue;
				int x=p[i].x,y=p[i].y;
				int nx=p[j].x,ny=p[j].y;
				if(nx<x||ny<y) continue;
				int dis=(nx-x+ny-y-1);
				if(t+dis>k) continue;
				dp[j][t+dis]=max(dp[j][t+dis],dp[i][t]+dis+1);
				ans=max(ans,dp[j][t+dis]+k-t-dis);
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}