#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
int N, K, M;
vector<int> R;
const long long INF = 1e18 + 123;
const int MAXN = 1000;
bool cached[MAXN+1][MAXN+1];
long long memo[MAXN+1][MAXN+1];
// dp(i) = minima suma de areas que cubren los puntos desde i hasta N-1
long long dp( int i, int rem_fotos ) {
if (i == N)
return 0;
if (cached[i][rem_fotos])
return memo[i][rem_fotos];
long long res = INF;
if (rem_fotos > 0) {
for (int j = i; j < N; j++) {
long long area_foto = (R[j] - R[i] + 1) * 1LL * (R[j] - R[i] + 1);
long long cur = area_foto + dp( j + 1, rem_fotos-1 );
res = min(res, cur);
}
}
cached[i][rem_fotos] = true;
memo[i][rem_fotos] = res;
return res;
}
long long take_photos(int n, int m, int k,
std::vector<int> r, std::vector<int> c) {
N = n;
R = r;
sort(R.begin(), R.end());
K = k;
M = m;
for (int i = 0; i < n; i++)
for (int k = 0; k <= n; k++)
cached[i][k] = false;
return dp( 0, K );
}
