/* 我们从要选点，形成 一个序列 ，可以看出这是一个经典的二维dp题

我们进行排列，然后dp

f[i][j]的i为以a[i]为结尾的序列，j为剩自由点数量

转移方程为 f[i][j]=max(f[i][j],f[t][j+d]+d+1)

f[t][j+d]+d+1为第t项结尾 变为 第i项结尾的数列里的数的个数

*/

//献上代码 (QWQ)

#include<bits/stdc++.h>

using namespace std;

int n,k,ans,f[501][101];//f[i][j]的i为以a[i]为结尾的序列，j为剩自由点数量

struct node{

int x,y;

}a[501];

bool cmp(node x,node y){//假设x优先级比y高

if(x.x==y.x)return x.y<y.y;

return x.x<y.x;

}

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);//排列先后顺序，方便dp 

for(int i=1;i<=n;i++){
	
	f[i][k]=1;//初始化 
	
	for(int j=0;j<=k;j++){//枚举自由点 
	
		for(int t=1;t<i;t++){
			
			if(a[t].x>a[i].x||a[t].y>a[i].y)continue;//不满足条件，退出 
			
			int dx=abs(a[i].x-a[t].x);
			
			int dy=abs(a[i].y-a[t].y);
			
			int d=dx+dy-1;//需要的自由点数量 
			
			if(j+d>k)continue; //不够，退出 
			
			f[i][j]=max(f[i][j],f[t][j+d]+d+1);//方程转移式 
			
		}
		
	}
	
}

for(int i=1;i<=n;i++){
	
	for(int j=0;j<=k;j++){
		
		ans=max(ans,f[i][j]+j);//选出最多的序列 
		
	}
	
}

cout<<ans;

return 0;

}