#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>

using namespace std;

typedef long double ld;

#define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)

#define sz(x) ((int) (x).size())
#define TASK "text"

const int inf = (int) 1.01e9;
const long long infll = (long long) 1.01e18;
const ld eps = 1e-9;
const ld pi = acos((ld) -1);

mt19937 mrand(random_device{} ());

int rnd(int x) {
  return mrand() % x;
}

const int maxn = (int) 2e3 + 5;

vector<int> xs, ys;

struct node {
  long long mnr, mxr, len;
  long long toass;
};

node st[4 * maxn];
long long vals[maxn];

void buildst(int v, int tl, int tr) {
  st[v].toass = -infll;
  if (tl == tr - 1) {
    st[v].mnr = ys[tl] + vals[tl];
    st[v].mxr = ys[tl] + vals[tl];
    st[v].len = vals[tl];
    return;
  }
  int tm = (tl + tr) / 2;
  buildst(2 * v, tl, tm);
  buildst(2 * v + 1, tm, tr);
  st[v].mnr = min(st[2 * v].mnr, st[2 * v + 1].mnr);
  st[v].mxr = max(st[2 * v].mxr, st[2 * v + 1].mxr);
  st[v].len = min(st[2 * v].len, st[2 * v + 1].len);
}

void push(int v, int r0, int r1) {
  if (st[v].toass == -infll) {
    return;
  }
  long long ry = st[v].toass;
  for (int i = 0; i < 2; i++) {
    int u = 2 * v + i;
    int ur = (!i ? r0 : r1);
    st[u].mnr = ry;
    st[u].mxr = ry;
    st[u].len = ry - (ys[ur - 1]);
    st[u].toass = ry;
  }
  st[v].toass = -infll;
}

void update(int v, int tl, int tr, int ly, long long ry) {
  if (tr <= ly) {
    return;
  }
  if (st[v].mnr >= ry) {
    return;
  }
  if (ly <= tl && st[v].mxr < ry) {
    st[v].mnr = ry;
    st[v].mxr = ry;
    st[v].len = ry - (ys[tr - 1]);
    st[v].toass = ry;
    return;
  }
  int tm = (tl + tr) / 2;
  push(v, tm, tr);
  update(2 * v, tl, tm, ly, ry);
  update(2 * v + 1, tm, tr, ly, ry);
  st[v].mnr = min(st[2 * v].mnr, st[2 * v + 1].mnr);
  st[v].mxr = max(st[2 * v].mxr, st[2 * v + 1].mxr);
  st[v].len = min(st[2 * v].len, st[2 * v + 1].len);
}

vector<int> evs[maxn];
vector<int> cols[maxn];
int cnt[maxn];
int lst[maxn];
int prv[maxn], nxt[maxn];

struct ColorfulEnclosure {
  long long minArea(int k, vector<int> px, vector<int> py, vector<int> c) {
    xs = px;
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    ys = py;
    sort(ys.begin(), ys.end());
    ys.erase(unique(ys.begin(), ys.end()), ys.end());
    for (int i = 0; i < sz(px); i++) {
      px[i] = lower_bound(xs.begin(), xs.end(), px[i]) - xs.begin();
      py[i] = lower_bound(ys.begin(), ys.end(), py[i]) - ys.begin();
    }
    vector<pair<pair<int, int>, int>> ps;
    for (int i = 0; i < sz(px); i++) {
      ps.push_back(make_pair(make_pair(py[i], px[i]), c[i]));
    }
    sort(ps.begin(), ps.end());
    long long res = 4 * infll;
    for (int x0 = 0; x0 < sz(xs); x0++) {
      for (int i = 0; i < sz(ps); i++) {
        if (ps[i].first.second < x0) {
          ps.erase(ps.begin() + i);
          i--;
        }
      }
      for (int i = 0; i < sz(xs); i++) {
        evs[i].clear();
      }
      for (int i = 0; i < sz(ys); i++) {
        cols[i].clear();
      }
      for (int i = 0; i < sz(ps); i++) {
        evs[ps[i].first.second].push_back(i);
        cols[ps[i].first.first].push_back(ps[i].second);
      }
      for (int i = 0; i < k; i++) {
        cnt[i] = 0;
      }
      int good = 0;
      for (int l = 0, r = 0; l < sz(ys); l++) {
        while (r < sz(ys) && good < k) {
          for (int i = 0; i < sz(cols[r]); i++) {
            int col = cols[r][i];
            good -= (cnt[col] > 0);
            cnt[col]++;
            good += (cnt[col] > 0);
          }
          r++;
        }
        vals[l] = (good == k ? ys[r - 1] - ys[l] : infll);
        for (int i = 0; i < sz(cols[l]); i++) {
          int col = cols[l][i];
          good -= (cnt[col] > 0);
          cnt[col]--;
          good += (cnt[col] > 0);
        }
      }
      buildst(1, 0, sz(ys));
      for (int i = 0; i < k; i++) {
        lst[i] = -1;
      }
      for (int i = 0; i < sz(ps); i++) {
        prv[i] = lst[ps[i].second];
        lst[ps[i].second] = i;
      }
      for (int i = 0; i < k; i++) {
        lst[i] = sz(ps);
      }
      for (int i = sz(ps) - 1; i >= 0; i--) {
        nxt[i] = lst[ps[i].second];
        lst[ps[i].second] = i;
      }
      for (int x1 = sz(xs); x1 > x0; x1--) {
        long long len = st[1].len;
        if (len >= infll / 2) {
          break;
        }
        res = min(res, len * (xs[x1 - 1] - xs[x0]));
        for (int i = 0; i < sz(evs[x1 - 1]); i++) {
          int id = evs[x1 - 1][i];
          int pid = prv[id], nid = nxt[id];
          if (pid >= 0) {
            nxt[pid] = nid;
          }
          if (nid < sz(ps)) {
            prv[nid] = pid;
          }
          int ly = (pid < 0 ? 0 : ps[pid].first.first + 1);
          int ry = (nid >= sz(ps) ? sz(ys) : ps[nid].first.first);
          update(1, 0, sz(ys), ly, (ry < sz(ys) ? ys[ry] : infll));
        }
      }
    }
    return res;
  }
};