#include <bits/stdc++.h>
using namespace std;
struct node
{
	int x,y;
}p[505];
bool cmp(node a,node b)
{
	if (a.x!=b.x)return a.x<b.x;
	return a.y<b.y;
}
int n,k,dp[505][505];
int main()
{
	int n,k;
	cin>>n>>k;
	for (int i=1;i<=n;i++)
	{
		cin>>p[i].x>>p[i].y;
	}
	sort(p+1,p+n+1,cmp);
	for (int i=1;i<=n;i++)
	{
		dp[i][1]=1;
		for (int j=1;j<=k;j++)
		{
			for (int t=1;t<i;t++)
			{
				if(p[t].x>p[i].x||p[t].y>p[i].y)continue;
				int dx=abs(p[i].x-p[t].x);
				int dy=abs(p[i].y-p[t].y);
				int d=dx+dy-1;
				if(j+d>k)continue;
				dp[i][j]=max(dp[i][j],dp[t][j+d]+d+1);
			}
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=k;j++)
		{
			ans=max(ans,j+dp[i][j]);
		}
	}
	cout<<ans;
	return 0;
}