#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, i;
  long long left, bottom, width, bestwidth;
  vector <long long> X;
  vector <long long> Y;
  vector <long long> D;

  bestwidth = 0xfffffffffffLL;

  for (i = 0; i < x.size(); i++) X.push_back(x[i]);
  for (i = 0; i < y.size(); i++) Y.push_back(y[i]);
  
  for (l = 0; l < X.size(); l++) {
    left = X[l];
    for (b = 0; b < Y.size(); b++) {
      bottom = Y[b];
      D.clear();
      for (i = 0; i < X.size(); i++) {
        if (X[i] >= left && Y[i] >= bottom) {
          width = X[i] - left;
          if (Y[i] - bottom > width) width = Y[i] - bottom;
          D.push_back(width);
        }
        if (D.size() >= K) {
          sort(D.begin(), D.end());
          width = D[K-1];
          if (width < bestwidth) bestwidth = width;
        }
        // cout << left << " " << bottom << " " << width << " " << n << " " << bestwidth << endl;
      }
    }
  }
  return (bestwidth + 2) * (bestwidth+2);
}