#include <bits/stdc++.h>
using namespace std;
const int MAXN=505;
int n,k,dp[MAXN][MAXN],ans=1;//dp[前i个点][插入j个新点]的最大序列数
struct edge{
	int x,y,s;
	friend bool operator <(edge a,edge b)
	{
		if(a.s==b.s) return a.x<b.x;
		else return a.s<b.s;
	}
}a[MAXN];
int id=0;

int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
	{
		id++;
		scanf("%d%d",&a[id].x,&a[id].y);
		a[id].s=a[id].x+a[id].y;
	}
	sort(a+1,a+1+n);
	//for(int i=1;i<=n;i++) printf("%d %d\n",a[i].x,a[i].y);
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=k;j++)
		{
			dp[i][j]=1;
			for(int l=1;l<i;l++)
			{
				if(a[l].x>a[i].x || a[l].y>a[i].y) continue;
				int t;
				t=a[i].x-a[l].x+a[i].y-a[l].y-1;//-1
				if(t<=j)
				{
					dp[i][j]=max(dp[i][j],dp[l][j-t]+t+1);
				}
			}
		}
	}
	for(int i=1;i<=n;i++) ans=max(ans,dp[i][k]);
	cout<<ans;
	return 0;
}