#include<bits/stdc++.h>
using namespace std;
struct node
{
	int x,y;
}a[501];
bool acmp(node a,node b)
{
	if(a.x==b.x) return a.y<b.y; 
    return a.x<b.x;
}
int f[501][101];
int they[501][101];
int main()
{
//	freopen("point4.in","r",stdin);
//	freopen("point4.out","w",stdout);
	//输入整理 
	int n,k;
	scanf("%d %d",&n,&k);
	for(int i=1;i<=n;i++) scanf("%d %d",&a[i].x,&a[i].y);
	sort(a+1,a+1+n,acmp);//x从小到大，x相等时y从小到大排序 

	//dp边界限定
	for(int i=1;i<=n;i++) for(int j=0;j<=k;j++) f[i][j]=1;
	
	//dp运算 
	int len;
	for(int i=n-1;i>=1;i--)//i=点号位 
	{
		for(int j=i+1;j<=n;j++)//j=目标点号位 
		{
			if(a[j].y<a[i].y) continue;//保证y上单调性 
			len=abs(a[j].x-a[i].x)+abs(a[j].y-a[i].y)-1;//求两点间距离 
			for(int s=0;s<=k-len;s++)
			{
				if(f[i][len]<=f[j][s]+len+1&&they[j][s]+len<=k)
				{
					if(f[i][len]==f[j][s]+len+1) 
					{
						if(they[i][len]>they[j][s]+len) they[i][len]=they[j][s]+len;
						continue;
					}//特判相等时自由点优劣势 
					 f[i][len]=f[j][s]+len+1; 
					 they[i][len]=they[j][s]+len;
				 }
			}
		}
	}
	
	//收尾统计 
	int ans=1;
	for(int i=1;i<=n;i++) f[i][0]+=k-they[i][0]; 
	for(int i=1;i<=n;i++) for(int j=1;j<=k;j++) f[i][j]=max(f[i][j-1],f[i][j]+k-they[i][j]);
	for(int i=1;i<=n;i++) ans=max(f[i][k],ans);
	printf("%d",ans);
	return 0;
}

注：

1.本代码中，they[i][j]表示f[i][j]最优状态时所用的自由点点数。

2.这里排序是x从小到大，x相等时y从小到大排序。

3.本dp按点排序顺序从后往前进行状态转移。