#include<bits/stdc++.h>
using namespace std;
struct node{
	int x;
	int y;
	int score = 0;
}l[505];
int n,k,score = 0;
bool cmp(node a,node b){
	if(a.x != b.x) return a.x < b.x;
	return a.y < b.y;
}
int main(){
//	freopen("point.in","r",stdin);
//	freopen("point.out","w",stdout);
	scanf("%d %d",&n,&k);
	for(int i = 0;i < n;++ i) scanf("%d %d",&l[i].x,&l[i].y);
	sort(l,l + n,cmp);
	for(int i = 0;i < n;++ i){
		l[i].score = 1;
		for(int j = 0;j < i;++ j) if((l[i].x - l[j].x == 1 && l[i].y == l[j].y) || l[i].y - l[j].y == 1 && l[i].x == l[j].x)
		l[i].score = max(l[i].score,l[j].score + 1);
		score = max(score,l[i].score);
	}
	
	if(k == 0){
		printf("%d",score);
	}
	else{
		printf("%d",score + k);
	}
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}