#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=510;
const ll INF=1e18;
vector<int> r, c;
ll memo[MAXN][MAXN];
ll respf;
int n, m, x;
ll dp(int ind, int k) {
// printf("chama %d %d\n", ind, k);
if(k<0) return INF;
if(ind==n) return 0;
if(memo[ind][k]!=-1) return memo[ind][k];
ll &resp=memo[ind][k];
resp=INF;
for(int j=ind; j<n; j++) {
ll custo=r[j]-r[ind]+1; custo*=custo;
resp=min(resp, custo+dp(j+1, k-1));
}
// printf("%d %d >> %lld\n", ind, k, resp);
return resp;
}
ll take_photos(int N, int M, int K, vector<int> R, vector<int> C) {
n=N; m=M; x=K;
r=R; c=C;
sort(r.begin(), r.end());
memset(memo, -1, sizeof(memo));
respf=dp(0, x);
return respf;
}
