#include<fstream>
#include<algorithm>
using namespace std;

short int a[5005][5005];
int n,k,m,i,j,nr,x,y;

int main()
{
	ifstream f("puncte5.in");
	ofstream g("puncte5.out");
	f >> m >> k;
	for (i=1;i<=m;i++)
	{
		f >> x >> y;
		a[x][y]++;
	}
	n=5000;
	for (i=2;i<=n;i++)
	{
		a[1][i]=a[1][i-1]+a[1][i];
		a[i][1]=a[i-1][1]+a[i][1];
	}
	for (i=2;i<=n;i++)
		for (j=2;j<=n;j++)
			a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+a[i][j];
	nr=n-1;
	for (i=n;i>=nr;i--)
		for (j=n;j>=nr;j--)
			while (a[i][j]-a[i-nr][j]-a[i][j-nr]+a[i-nr][j-nr]>=k)
				nr--;
	g << nr;
	return 0;
}