#include<bits/stdc++.h>
using namespace std;
int xand[2]={0,1},yand[2]={1,0},xz[505],yz[505],use[105][105],mp[105][105],maxx=200,maxy=200,n,k,ans,l[105][105][105];
void dfs(int x,int y,int ands,int len){
//	cout<<x<<" "<<y<<" "<<ands<<endl;
	if(l[x][y][ands])return;
	l[x][y][ands]=1;
	ans=max(ans,len);
	for(int i=0;i<2;i++){
		int xx=x+xand[i],yy=y+yand[i];
		if(xx<=105&&yy<=105&&xx>0&&yy>0&&!use[xx][yy]){
			if(mp[xx][yy]){
				use[xx][yy]=1;
				dfs(xx,yy,ands,len+1);
				use[xx][yy]=0;
			}else if(ands){
				use[xx][yy]=1;
				dfs(xx,yy,ands-1,len+1);
				use[xx][yy]=0;
			}
		}
	}
}
int main(){
	freopen("point.in","r",stdin);
	freopen("point.out","w",stdout);
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>xz[i]>>yz[i];
		mp[xz[i]][yz[i]]=1;
		maxx=min(maxx,xz[i]);
		maxy=min(maxy,yz[i]);
	}
	for(int i=1;i<=maxx;i++){
		for(int j=1;j<=maxy;j++){
			if(mp[i][j])dfs(i,j,k,1);
			else dfs(i,j,k-1,1);
		}
	}
	cout<<ans;
	return  0;
}