#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=505;
int n,k,rd[N],vis[N],ans,dp[N][N];
struct Node{
	int x,y;
}a[N];
bool cmp(Node a,Node b){
	if(a.x!=b.x) return a.x<b.x;
	return a.y<b.y;
}
struct edge{
	int v,w;
};
vector<edge> e[N];
void dfs(int x){
	vis[x]=1;
	for(auto i:e[x]){
		rd[i.v]--;
		for(int j=0;j<=k-i.w;j++){
			dp[i.v][j+i.w]=max(dp[i.v][j+i.w],dp[x][j]+1);
			ans=max(ans,dp[i.v][j+i.w]);
		}
		if(rd[i.v]==0){
			dfs(i.v);
		}
	}
}
signed main(){
	scanf("%lld%lld",&n,&k);
	for(int i=1;i<=n;i++){
		scanf("%lld%lld",&a[i].x,&a[i].y);
	}
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			if(a[j].y>=a[i].y){
				e[i].push_back({j,(a[j].x-a[i].x)+(a[j].y-a[i].y)-1});
				rd[j]++;
			}
		}
	}
	for(int j=1;j<=n;j++){
		if(rd[j]==0&&!vis[j]){
			dp[j][0]=1;
			dfs(j);
		}
	}
	printf("%lld",ans+k);
}