#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,k,m,f[501][501][2],x,y,maxn=0;
bool a[501][501];
int check(int xx,int yy){
	int maxx=0;
	if (!a[xx][yy]) return 0;
	memset(f,0,sizeof(f));
	f[xx][yy][0]=1,f[xx][yy][1]=0;
	for (int i=xx;i<=n;i++)
		for (int j=yy;j<=n;j++){
			if (i==xx&&j==yy) continue;
			if (a[i][j]){
				if (f[i-1][j][1]<k&&f[i][j-1][1]<k){
					if (f[i-1][j][0]>f[i][j-1][0]) f[i][j][0]=f[i-1][j][0]+1,f[i][j][1]=f[i-1][j][1];
					else if (f[i-1][j][0]>f[i][j-1][0]) f[i][j][0]=f[i][j-1][0]+1,f[i][j][1]=f[i][j-1][1];
					else if (f[i-1][j][1]<f[i][j-1][1]) f[i][j][0]=f[i-1][j][0]+1,f[i-1][j][1]=f[i][j][1];
					else f[i][j][0]=f[i][j-1][0]+1,f[i][j][1]=f[i][j-1][1]+1;
				}
				else if (f[i-1][j][1]>k&&f[i][j-1][1]<=k) f[i][j][0]=f[i][j-1][0]+1,f[i][j][1]=f[i][j-1][1];
				else if (f[i-1][j][1]<=k&&f[i][j-1][1]>k) f[i][j][0]=f[i-1][j][0]+1,f[i][j][1]=f[i-1][j][1];
				else f[i][j][0]=0,f[i][j][1]=k+1;
			}
			else{
				if (f[i-1][j][1]<k&&f[i][j-1][1]<k){
					if (f[i-1][j][0]>f[i][j-1][0]) f[i][j][0]=f[i-1][j][0]+1,f[i][j][1]=f[i-1][j][1]+1;
					else if (f[i-1][j][0]>f[i][j-1][0]) f[i][j][0]=f[i][j-1][0]+1,f[i][j][1]=f[i][j-1][1]+1;
					else if (f[i-1][j][1]<f[i][j-1][1]) f[i][j][0]=f[i-1][j][0]+1,f[i-1][j][1]=f[i][j][1]+1;
					else f[i][j][0]=f[i][j-1][0]+1,f[i][j][1]=f[i][j-1][1]+1;
				}
				else if (f[i-1][j][1]>k&&f[i][j-1][1]<=k) f[i][j][0]=f[i][j-1][0]+1,f[i][j][1]=f[i][j-1][1]+1;
				else if (f[i-1][j][1]<=k&&f[i][j-1][1]>k) f[i][j][0]=f[i-1][j][0]+1,f[i][j][1]=f[i-1][j][1]+1;
				else f[i][j][0]=0,f[i][j][1]=k+1;
			}
		}
//	cout<<xx<<' '<<yy<<endl;
//	for (int i=xx;i<=n;i++){
//		for (int j=yy;j<=n;j++)
//			cout<<f[i][j][0]<<' ';
//		cout<<endl;
//	}
//	for (int i=xx;i<=n;i++){
//		for (int j=yy;j<=n;j++)
//			cout<<f[i][j][1]<<' ';
//		cout<<endl;
//	}	
	for (int i=xx;i<=n;i++)
		for (int j=yy;j<=n;j++)
			if (f[i][j][0]>maxx&&f[i][j][1]<=k)
				maxx=f[i][j][0]+(k-f[i][j][1]);
//	cout<<maxx<<endl;
	return maxx;
}
signed main(){
// 	freopen("point.in","r",stdin);
// 	freopen("point.out","w",stdout);
	cin>>n>>k;
	while (n--){
		cin>>x>>y;
		a[x][y]=1;
		m=max(m,max(x,y));
	}
	n=m;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
			maxn=max(maxn,check(i,j));
	cout<<maxn+2;
	return 0;
}
/*
8 2
3 1
3 2
3 3
3 6
1 2
2 2
5 5
5 3

4 100
10 10
15 25
20 20
30 30
*/