#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=505;
int n,l;
int maxn;
struct Node{
	int x,y;
}a[N],b[N];
int dp[N][N];       //dp[i][j]表示前i个点增j个点的最大值 
int f[N][N];
bool cmp(Node x,Node y){
	if(x.x==y.x)return x.y<y.y;
	return x.x<y.x;
}
bool cmp1(Node x,Node y){
	if(x.y==y.y)return x.x<y.x;
	return x.y<y.y;
}
signed main(){
    cin>>n>>l;
    for(int i=1;i<=n;i++){
    	cin>>a[i].x>>a[i].y;
    	b[i]=a[i];
    }
    sort(b+1,b+1+n,cmp);
    for(int i=1;i<=n;i++){
    	dp[i][0]=1;
    	for(int j=1;j<i;j++){
    		if((b[i].x==b[j].x+1&&b[i].y==b[j].y)||(b[i].y==b[j].y+1&&b[i].x==b[j].x)){
    			dp[i][0]=max(dp[j][0]+1,dp[i][0]);
    		}
    	}
    	for(int j=1;j<=l;j++){
    		dp[i][j]=j+1;
    		for(int k=1;k<i;k++){
    			if(b[i].x>b[k].x&&b[i].x-b[k].x-1<=j&&b[i].y==b[k].y){
    				int u=b[i].x-b[k].x-1;
    				dp[i][j]=max(dp[i][j],dp[k][j-u]+u+1);
    			}
    			if(b[i].y>b[k].y&&b[i].y-b[k].y-1<=j&&b[i].x==b[k].x){
    				int u=b[i].y-b[k].y-1;
    				dp[i][j]=max(dp[i][j],dp[k][j-u]+u+1);
    			}
    			if((b[i].y>b[k].y)&&(b[i].x>b[k].x)&&(b[i].y-b[k].y-1)+(b[i].x-b[k].x-1)<=j){
    				int u=(b[i].y-b[k].y-1)+(b[i].x-b[k].x-1);
    				dp[i][j]=max(dp[i][j],dp[k][j-u]+u+1);
    			}
    		}
    	}
    }
    for(int i=1;i<=n;i++){
    	b[i]=a[i];
    }
    sort(b+1,b+1+n,cmp1);
    for(int i=1;i<=n;i++){
    	f[i][0]=1;
    	for(int j=1;j<i;j++){
    		if((b[i].x==b[j].x+1&&b[i].y==b[j].y)||(b[i].y==b[j].y+1&&b[i].x==b[j].x)){
    			f[i][0]=max(f[j][0]+1,f[i][0]);
    		}
    	}
    	for(int j=1;j<=l;j++){
    		f[i][j]=j+1;
    		for(int k=1;k<i;k++){
    			if(b[i].x>b[k].x&&b[i].x-b[k].x-1<=j&&b[i].y==b[k].y){
    				int u=b[i].x-b[k].x-1;
    				f[i][j]=max(f[i][j],f[k][j-u]+u+1);
    			}
    			if(b[i].y>b[k].y&&b[i].y-b[k].y-1<=j&&b[i].x==b[k].x){
    				int u=b[i].y-b[k].y-1;
    				f[i][j]=max(f[i][j],f[k][j-u]+u+1);
    			}
    			if((b[i].x>b[k].x)&&(b[i].y>b[k].y)&&(b[i].y-b[k].y-1)+(b[i].x-b[k].x-1)<=j){
    				int u=(b[i].y-b[k].y-1)+(b[i].x-b[k].x-1);
    				f[i][j]=max(f[i][j],f[k][j-u]+u+1);
    			}
    		}
    	}
    }
    for(int i=1;i<=n;i++){
    	for(int j=0;j<=l;j++){
    		maxn=max(maxn,max(dp[i][j],f[i][j]));
//    		if(f[i][j]==21)cout<<i<<" "<<j<<" "<<1<<"\n";
//    		else if(dp[i][j]==21)cout<<i<<" "<<j<<" "<<2<<"\n"; 
    	}
    }
    cout<<maxn;
	return 0;
}

//P8816 [CSP-J 2022] 上升点列