#include<cstdio>
#include<algorithm>
#include<queue>
#define N 114514
#define int long long 
#define inf 2147483647
using namespace std;
priority_queue<int,vector<int>,greater<int> >q;
struct node{int x,y;}a[N];
int n,k;
bool cmpx(node x,node y){return x.x<y.x;}
bool cmpy(node x,node y){return x.y<y.y;}
int dis(node x,node y){return (x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y);}
struct kdt{
	int lx[N],rx[N],ly[N],ry[N],lson[N],rson[N];
	#define lc lson[p]
	#define rc rson[p]
	int ldis(int p,node x){
		int ax=max(x.x-lx[p],rx[p]-x.x);
		int ay=max(x.y-ly[p],ry[p]-x.y);
		return ax*ax+ay*ay;
	}
	int pushup(int p){
		lx[p]=rx[p]=a[p].x;
		ly[p]=ry[p]=a[p].y;
		if(lc){
			lx[p]=min(lx[lc],lx[p]),rx[p]=max(rx[lc],rx[p]);
			ly[p]=min(ly[lc],ly[p]),ry[p]=max(ry[lc],ry[p]);
		}
		if(rc){
			lx[p]=min(lx[rc],lx[p]),rx[p]=max(rx[rc],rx[p]);
			ly[p]=min(ly[rc],ly[p]),ry[p]=max(ry[rc],ry[p]);
		}
		return p;
	}
	int build(int l,int r){
		if(r<l)return 0;
		int p=l+((r-l)>>1);
		if(l&1)nth_element(a+l,a+p,a+r+1,cmpx);
		else nth_element(a+l,a+p,a+r+1,cmpy);
		lc=build(l,p-1);rc=build(p+1,r);
		return pushup(p);
	}
	void work(int l,int r,node x){
		if(r<l)return;
		int p=l+((r-l)>>1),val=dis(a[p],x);
		if(a[p].x!=x.x&&a[p].y!=x.y&&val>q.top())q.pop(),q.push(val);
		if(l==r)return;
		int vall=ldis(lc,x),valr=ldis(rc,x),mn=q.top();
		if(vall>mn&&valr>mn){
			if(vall>=valr){
				work(l,p-1,x);
				if(valr>q.top())work(p+1,r,x);
			}else{
				work(p+1,r,x);
				if(vall>q.top())work(l,p-1,x);
			}
		}else if(vall>mn)work(l,p-1,x);
		else if(valr>mn)work(p+1,r,x);
		return;
	}
}t;
signed main(){
	scanf("%lld%lld",&n,&k);
	for(int i=1;i<=k*2;i++)q.push(0);
	for(int i=1;i<=n;i++){
		int x,y;
		scanf("%lld%lld",&x,&y);
		a[i]=(node){x,y}; 
	}
	t.build(1,n);
	for(int i=1;i<=n;i++)t.work(1,n,a[i]);
	printf("%lld",q.top());
	return 0;
}