//team09 
#include<iostream>
#include<algorithm>
using namespace std;
int f[501][501],xx,n,k,ans;
struct node{
    int x,y;
}a[501];
bool cmp(node x,node y){//贪心排序 
    if(x.x==y.x){
		return x.y<y.y;
	}
    return x.x<y.x;
}
main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
		f[i][0]=1;
	}
    for(int i=1;i<=n;i++){
		scanf("%d%d",&a[i].x,&a[i].y);
	}
    sort(a+1,a+n+1,cmp);
    for(int z=0;z<=k;z++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(a[j].x<a[i].x||a[j].y<a[i].y){//判断是否符合要求 
					continue;
				}
                int sum=a[j].x-a[i].x+a[j].y-a[i].y-1;
                if(sum+z>k){
					continue;
				}
                f[j][z+sum]=max(f[j][z+sum],f[i][z]+sum+1);//改变数值 
                ans=max(f[j][z+sum]+(k-z-sum),ans);//比较 
            }
        }
    }
    printf("%d\n",ans-1);//输出 
    return 0;
}
/**************************************************************
	Problem: 2408
	User: admin
	Language: C++
	Result: Accepted
	Time:368 ms
	Memory:3060 kb
****************************************************************/