#include <string>
#include <vector>
#include <list>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

#define VIT(i, v) for (i = 0; i < v.size(); i++) 
#define IT(it, ds) for (it = ds.begin(); it != ds.end(); it++)
#define O1(v) cout << v << endl
#define O2(v1, v2) cout << v1 << " " << v2 << endl
#define O3(v1, v2, v3) cout << v1 << " " << v2 << " " << v3 << endl
#define OVEC(v) { int iii; VIT(iii, v) cout << v[iii] << " " ; cout << endl; }
typedef vector <int> IVec;

class MinimumSquare {
  public:
    long long minArea(vector <int> x, vector <int> y, int K);
};

long long MinimumSquare::minArea(vector <int> x, vector <int> y, int K)
{
  int l, b, w, i, n;
  long long left, bottom, width, bestwidth;
  vector <long long> X;
  vector <long long> Y;
  multimap <long long, long long> S;
  multimap <long long, long long>::iterator sit;

  for (i = 0; i < x.size(); i++) S.insert(make_pair(x[i], y[i]));
  for (sit = S.begin(); sit != S.end(); sit++) {
    X.push_back(sit->first);
    Y.push_back(sit->second);
  }
  bestwidth = 0x8ffffffffffLL;

  for (l = 0; l < X.size(); l++) {
    left = X[l];
    for (b = 0; b < Y.size(); b++) {
      bottom = Y[b];
      for (w = 0; w < X.size(); w++) {
        width = X[w] - left;
        if (Y[w] - bottom > width) width = Y[w] - bottom;
        n = 0;
        for (i = 0; i < X.size(); i++) {
          if (X[i] >= left && X[i]-left <= width &&
              Y[i] >= bottom && Y[i]-bottom <= width) n++;
        }
        if (n >= K && width < bestwidth) bestwidth = width;
        // cout << left << " " << bottom << " " << width << " " << n << " " << bestwidth << endl;
      }
    }
  }
  return (bestwidth + 2) * (bestwidth+2);
}