#define REP(i, a, b) for(int i = a; i <= b; i ++)
#define REPG(i, x) for(int i = head[x]; i; i = g[i].nxt)
#define clr(x, y) memset(x, y, sizeof(x));
 
using namespace std;
 
typedef long long LL;
typedef double LF;
 
LL (LL a, LL b){return a > b ? a : b;}
LL Min(LL a, LL b){return a < b ? a : b;}
LL abs(LL x){return x > 0 ? x : -x;}
 
const int MAXN = 1e5 + 15;
const LL oo = 1e18;
 
struct Node{
    LL dis;
    inline bool operator < (const Node &a) const{return a.dis < dis;}
};
priority_queue <Node> q;
int D, n, m, rt;
 
struct P{
    int d[2], mx[2], mn[2], l, r;
    int& operator[](int x){return d[x];}
}p[MAXN];
bool operator < (P a, P b){return a[D] < b[D];}
 
struct kd_tree{
    P T, t[MAXN];
    LL sqr(int x){return 1ll * x * x;}
    LL getdist(P a, P b){
        LL ret = 0;
        for(int i = 0; i < 2; i ++) ret += sqr(a[i] - b[i]);
        return ret;
    }
    void update(int k){
        P lson = t[t[k].l], rson = t[t[k].r];
        for(int i = 0; i < 2; i ++){
            if(t[k].l) t[k].mn[i] = min(t[k].mn[i], lson.mn[i]), t[k].mx[i] = max(t[k].mx[i], lson.mx[i]);
            if(t[k].r) t[k].mn[i] = min(t[k].mn[i], rson.mn[i]), t[k].mx[i] = max(t[k].mx[i], rson.mx[i]);
        }
    }
    int build(int l, int r, int now){
        D = now; int mid = l + r >> 1;
        nth_element(p + l, p + mid, p + r + 1);
        t[mid] = p[mid];
        for(int i = 0; i < 2; i ++) t[mid].mn[i] = t[mid].mx[i] = t[mid][i];
        if(l < mid) t[mid].l = build(l, mid - 1, now ^ 1);
        if(r > mid) t[mid].r = build(mid + 1, r, now ^ 1);
        update(mid);
        return mid;
    }
    LL get(int k, P p){
        LL ret = 0;
        for(int i = 0; i < 2; i ++) ret += Max(sqr(t[k].mn[i] - p[i]), sqr(t[k].mx[i] - p[i]));
        return ret;
    }
    void qry(int k){
        LL d, dl = 0, dr = 0;
        d = getdist(t[k], T); if(d > q.top().dis){q.pop(); Node tmp = (Node){d}; q.push(tmp);}
        if(t[k].l) dl = get(t[k].l, T);
        if(t[k].r) dr = get(t[k].r, T);
        if(dl > dr){
            if(dl > q.top().dis) qry(t[k].l);
            if(dr > q.top().dis) qry(t[k].r);
        }
        else {
            if(dr > q.top().dis) qry(t[k].r);
            if(dl > q.top().dis) qry(t[k].l);
        }
    }
    void query(P p){T = p; qry(rt);}
}kd;
 
inline int read(){
    int r = 0, z = 1; char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') z = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9'){r = r * 10 + ch - '0'; ch = getchar();}
    return r * z;
}
 
void work(){
    n = read(), m = read(); m *= 2;
    for(int i = 1; i <= n; i ++) p[i][0] = read(), p[i][1] = read();
    
    rt = kd.build(1, n, 0);
    for(int i = 1; i <= m; i ++){
        Node tmp = (Node){0};
        q.push(tmp);
    }
    for(int i = 1; i <= n; i ++) kd.query(p[i]);
    //for(int i = 1; i < m; i ++){cout<<q.top().dis<<" ";q.pop();} puts("");
    printf("%lldn", q.top().dis);
    //cout<<p[1][0]<<" "<<p[1][1]<<" "<<p[3][0]<<" "<<p[3][1]<<endl;
    //cout<<kd.getdist(p[1], p[3])<<endl;
}
  
int main(){
    work();
    return 0;
}