#include<bits/stdc++.h>
using namespace std;
int n,k;
int dp[505][105]; 
struct node
{
	int x,y;
}a[505];
bool cmp(node p,node q)
{
	if(p.x!=q.x)
	{
		return p.x<=q.x;
	}
	return p.y<q.y;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].x>>a[i].y;
	}
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++)
	{
		dp[i][k]=1;
		for(int j=0;j<=k;j++)
		{
			for(int k=1;k<i;k++)
			{
				if(a[k].y>a[i].y && a[k].x>a[i].x)
				{
					int d=abs(a[i].x-a[k].x)+abs(a[i].y-a[k].y)-1;
					if(j+d<=k)
					{
						dp[i][j]=max(dp[i][j],dp[k][j+d]+d+1);
					}
				}
			}
		}
	}
	int maxx=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=k;j++)
		{
			maxx=max(maxx,dp[i][j]);
		}
	}
	cout<<maxx;
	return 0;
}