#include<bits/stdc++.h>
#define N 510
using namespace std;
struct node{int x,y;}d[N];
bool cmp(node a,node b){return a.x+a.y<b.x+b.y;}
int n,k,ans=0;
int m[N][N];
int dp[N],cnt[N];
int main(){
	/*freopen("point.in","r",stdin);
	freopen("point.out","w",stdout);*/
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&d[i].x,&d[i].y);
	sort(d+1,d+1+n,cmp);
	for(int i=1;i<=n;i++) {
		dp[i]=1;
		for(int j=1;j<=n;j++){
			m[i][j]=-1;
			if(j==i) continue;
			else if(d[j].x>=d[i].x && 
			d[j].y>=d[i].y && d[j].x-d[i].x+d[j].y-d[i].y>0)
			    m[i][j]=d[j].x-d[i].x+d[j].y-d[i].y-1;
		}
	}	
	for(int i=1;i<=n;i++){
	   for(int j=1;j<=n;j++){
	   	    if(m[i][j]<0) continue;
	   	    if(i==j) continue;
			if(dp[j]<dp[i]+m[i][j]+1 && cnt[i]+m[i][j]<=k) {
			    dp[j]=dp[i]+m[i][j]+1;
			    cnt[j]=cnt[i]+m[i][j];
			} 
			else if(dp[j]==dp[i]+m[i][j]+1 && cnt[i]+m[i][j]<cnt[j] && cnt[i]+m[i][j]<=k)  
			    cnt[j]=cnt[i]+m[i][j];
	   }
    }
	for(int i=1;i<=n;i++) ans=max(ans,dp[i]+k-cnt[i]);
	printf("%d",ans);
	return 0;
}