#include <bits/stdc++.h>
using namespace std;
struct node{
	int x,y;
}a[505];
int dp[505][105];//到第i个点时用了j次机会的最大长度
bool cmp(node a,node b)
{
	if(a.x != b.x) return a.x < b.x;
	return a.y < b.y;
}
int main()
{
	int n,k;
	cin >> n >> k;
	for(int i = 1;i <= n;i++)
	{
		cin >> a[i].x >> a[i].y;
	}
	sort(a + 1,a + n + 1,cmp);
	int ans = -1e9;
	for(int i = 1;i <= n;i++)
	{
		for(int j = 0;j <= k;j++) dp[i][j] = j + 1;
	}
	for(int i = 2;i <= n;i++)
	{
		for(int j = 0;j <= k;j++)
		{
			for(int t = 1;t < i;t++)
			{
				if(a[i].x < a[t].x || a[i].y < a[t].x) continue;
				int dis = abs(a[i].x - a[t].x) + abs(a[i].y - a[t].y) - 1;
				if(dis > j) continue;
				dp[i][j] = max(dp[i][j],dp[t][j - dis] + dis + 1);
			}
		}
		ans = max(ans,dp[i][k]);
	}
	cout << ans;
 }