#include<bits/stdc++.h>
using namespace std;

//dp状态
//dp[i][j]以第i个点结尾并且补j个点时构成的最长上升子序列
//状态转移方程：  if（满足上升） dp[i][j]=max(dp[i][j],dp[t][j-d]+d+1) 
const int MAXN=1e8;

struct point
{
	int x,y;
}a[MAXN];

int dis(int x1,int y1,int x2,int y2)
{
	int d=abs(x1-x2)+abs(y1-y2)-1;
//	int d=x1-x2+y1-y2-1;
	return d;
}

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

signed main()
{
//	freopen("1.in","r",stdin);
	int n,k;
	cin>>n>>k;
	vector<vector<int> > dp(n+1,vector<int>(k,1));

	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++)
			dp[i][j]=j+1; // 直接在 i 点前插入 j 个点
	}
	
	
	// 类似最长上升子序列
	for(int i=2;i<=n;i++)
	{
		for(int j=i-1;j>=1;j--)
		{
			if(a[j].y>a[i].y)
				continue;
			int d=dis(a[i].x,a[i].y,a[j].x,a[j].y);
			for(int s=d;s<=k;s++)
			{
				dp[i][s]=max(dp[i][s],dp[j][s-d]+d+1);
			}
		}
	}
	
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		ans=max(ans,dp[i][k]);
	}

	cout<< ans;

}