#include<bits/stdc++.h>
using namespace std;
int n,k,f[505][505];
struct cspnb{
	int x,y;
}a[505];
bool cmp(cspnb qq,cspnb ww){
	if(qq.x	==ww.x)return qq.y<ww.y;
	return qq.x<ww.x ;
}
int get(int xa,int ya,int xb,int yb) 
{
	return max(xa-xb,xb-xa)+max(ya-yb,yb-ya)-1;
}
int 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 j=0;j<=k;j++)f[i][j]=1+j;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<i;j++){
			int len=get(a[i].x,a[i].y,a[j].x,a[j].y);
			if(len>k)continue;
			for(int g=len;g<=k;g++)f[i][g]=max(f[i][g],f[j][g-len]+len+1);
			
		}
		
	}
	int ans=-1;
	for(int i=1;i<=n;i++){
		ans=max(f[i][k],ans);
	}
	cout<<ans-1;
}