#include "stdio.h"
#include "stdlib.h"
#include "memory.h"
struct Node{
	int i,j,parent;
};
Node data[16001];
int col[2][10001];  //  col[i%2][j]记录i行j列在data中的下标
int N,K;

int Find(int k);
void Union(int p1,int p2);
int compare(const void* a,const void* b)
{
	Node *p=(Node*)a;
	Node *q=(Node*)b;
	if(p->i!=q->i)
		return p->i-q->i;
	else
		return p->j-q->j;
}
int cmp(const void*a,const void* b)
{
	Node* p=(Node*)a;
	Node* q=(Node*)b;
	return p->parent-q->parent;
}
int main(int argc, char* argv[])
{
    scanf("%d %d",&N,&K);
	int i;
	for(i=1;i<=N;i++)
	{
		scanf("%d %d",&data[i].i,&data[i].j);
		data[i].parent=-1;
	}
	qsort(&data[1],N,sizeof(Node),compare);
	int line=0;
	col[0][data[1].j]=1;
    for(i=2;i<=N;i++)
	{
		int p1=0,p2=0;
		if(data[i].i!=data[i-1].i) 
		{
			line++;
			memset(col[line%2],0,sizeof(col[line%2]));
		}
		if(data[i].i==data[i-1].i && data[i].j==data[i-1].j+1)
			p1=Find(i-1);
		if(line==0)          //  the first line 
		{
			col[0][data[i].j]=i;
		}
		else                 //  after the first line
		{
			if(col[(line-1)%2][data[i].j] && data[col[(line-1)%2][data[i].j]].i+1==data[i].i)
				p2=Find(col[(line-1)%2][data[i].j]);
			col[line%2][data[i].j]=i;
		}
		if(p1==0&&p2!=0)
			Union(p2,i);
		else if(p1!=0&&p2==0)
			Union(p1,i);
		else if(p1!=0&&p2!=0)
		{
			if(p1!=p2)
				Union(p1,p2);
			Union(p1,i);	
		}
	}
	qsort(&data[1],N,sizeof(Node),cmp);
	int sum=0;
	for(i=1;i<=K;i++)
		sum+=data[i].parent;
	printf("%d",-sum);
	return 0;
}

int Find(int k)
{
	if(data[k].parent<0)
		return k;
	int p=Find(data[k].parent);
	data[k].parent=p;
	return p;
}

void Union(int p1,int p2)
{
	data[p1].parent+=data[p2].parent;
	data[p2].parent=p1;
}