#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int UI;

int read(){
    int sgn=0,x=0;
    char c=getchar();
    while(!isdigit(c)) sgn|=(c=='-'),c=getchar();
    while(isdigit(c)) x=x*10+c-'0',c=getchar();
    return sgn?-x:x;
}

const int N=510;

struct points{
    int x,y;
}p[N];

int n,k;

int g[N][N],f[N][110];

bool cmp(points a,points b){
    return a.x==b.x?a.y<b.y:a.x<b.x;
}

void init(){
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            g[i][j]=abs(p[i].x-p[j].x)+abs(p[i].y-p[j].y)-1;
        }
    }
}

int main(){

    n=read(),k=read();
    for(int i=1; i<=n; i++){
        p[i].x=read(),p[i].y=read();
    }

    sort(p+1,p+1+n,cmp);

   // for(int i=1; i<=n; i++){
   //     cout<<p[i].x<<" "<<p[i].y<<endl;
   // }

    init();

    for(int i=0; i<=k; i++) f[1][i]=i+1;

    for(int i=2; i<=n; i++){
        f[i][0]=1;
        for(int j=1; j<i; j++){
            if(p[j].y>p[i].y) continue;
            if(p[j].x>p[i].x) continue;
            for(int l=g[i][j]; l<=k; l++){
                f[i][l]=max(f[i][l],f[j][l-g[i][j]]+g[i][j]+1);
            }
        }
    }

   // for(int i=1; i<=n; i++){
    //    for(int j=0; j<=k; j++){
    //        cout<<i<<' '<<j<<' '<<f[i][j]<<endl;
   //     }
   // }

    int ans=0;
    for(int i=1; i<=n; i++) ans=max(ans,f[i][k]);

    printf("%d\n",ans);

    return 0;
}